Efnisyfirlit

• Cover
• Preface to the Second Edition
• Preface to the First Edition
• Intended Audience
• What and How
• Abbreviations and Notation
• About the Companion Website
• 1 Formulations
• 1.1 Introduction
• 1.2 What Is an Integer Program?
• 1.3 Formulating IPs and BIPs
• 1.4 The Combinatorial Explosion
• 1.5 Mixed Integer Formulations
• 1.6 Alternative Formulations
• 1.7 Good and Ideal Formulations
• 1.8 Notes
• 1.9 Exercises
• 2 Optimality, Relaxation, and Bounds
• 2.1 Optimality and Relaxation
• 2.2 Linear Programming Relaxations
• 2.3 Combinatorial Relaxations
• 2.4 Lagrangian Relaxation
• 2.5 Duality
• 2.6 Linear Programming and Polyhedra
• 2.7 Primal Bounds: Greedy and Local Search
• 2.8 Notes
• 2.9 Exercises
• 3 Well‐Solved Problems
• 3.1 Properties of Easy Problems
• 3.2 IPs with Totally Unimodular Matrices
• 3.3 Minimum Cost Network Flows
• 3.4 Special Minimum Cost Flows
• 3.5 Optimal Trees
• 3.6 Submodularity and Matroids
• 3.7 Two Harder Network Flow Problems*
• 3.8 Notes
• 3.9 Exercises
• 4 Matchings and Assignments
• 4.1 Augmenting Paths and Optimality
• 4.2 Bipartite Maximum Cardinality Matching
• 4.3 The Assignment Problem
• 4.4 Matchings in Nonbipartite Graphs
• 4.5 Notes
• 4.6 Exercises
• 5 Dynamic Programming
• 5.1 Some Motivation: Shortest Paths
• 5.2 Uncapacitated Lot‐Sizing
• 5.3 An Optimal Subtree of a Tree
• 5.4 Knapsack Problems
• 5.5 The Cutting Stock Problem*
• 5.6 Notes
• 5.7 Exercises
• 6 Complexity and Problem Reductions
• 6.1 Complexity
• 6.2 Decision Problems, and Classes and
• 6.3 Polynomial Reduction and the Class
• 6.4 Consequences of or
• 6.5 Optimization and Separation
• 6.6 The Complexity of Extended Formulations
• 6.7 Worst‐Case Analysis of Heuristics
• 6.8 Notes
• 6.9 Exercises
• 7 Branch and Bound
• 7.1 Divide and Conquer
• 7.2 Implicit Enumeration
• 7.3 Branch and Bound: an Example
• 7.4 LP‐Based Branch and Bound
• 7.5 Using a Branch‐and‐Bound/Cut System
• 7.6 Preprocessing or Presolve
• 7.7 Notes
• 7.8 Exercises
• 8 Cutting Plane Algorithms
• 8.1 Introduction
• 8.2 Some Simple Valid Inequalities
• 8.3 Valid Inequalities
• 8.4 A Priori Addition of Constraints
• 8.5 Automatic Reformulation or Cutting Plane Algorithms
• 8.6 Gomory’s Fractional Cutting Plane Algorithm
• 8.7 Mixed Integer Cuts
• 8.8 Disjunctive Inequalities and Lift‐and‐Project
• 8.9 Notes
• 8.10 Exercises
• 9 Strong Valid Inequalities
• 9.1 Introduction
• 9.2 Strong Inequalities
• 9.3 0–1 Knapsack Inequalities
• 9.4 Mixed 0–1 Inequalities
• 9.5 The Optimal Subtour Problem
• 9.6 Branch‐and‐Cut
• 9.7 Notes
• 9.8 Exercises
• 10 Lagrangian Duality
• 10.1 Lagrangian Relaxation
• 10.2 The Strength of the Lagrangian Dual
• 10.3 Solving the Lagrangian Dual
• 10.4 Lagrangian Heuristics
• 10.5 Choosing a Lagrangian Dual
• 10.6 Notes
• 10.7 Exercises
• 11 Column (and Row) Generation Algorithms
• 11.1 Introduction
• 11.2 The Dantzig–Wolfe Reformulation of an IP
• 11.3 Solving the LP Master Problem: Column Generation
• 11.4 Solving the Master Problem: Branch‐and‐Price
• 11.5 Problem Variants
• 11.6 Computational Issues
• 11.7 Branch‐Cut‐and‐Price: An Example*
• 11.8 Notes
• 11.9 Exercises
• 12 Benders’ Algorithm
• 12.1 Introduction
• 12.2 Benders’ Reformulation
• 12.3 Benders’ with Multiple Subproblems
• 12.4 Solving the Linear Programming Subproblems
• 12.5 Integer Subproblems: Basic Algorithms*
• 12.6 Notes
• 12.7 Exercises
• 13 Primal Heuristics
• 13.1 Introduction
• 13.2 Greedy and Local Search Revisited
• 13.3 Improved Local Search Heuristics
• 13.4 Heuristics Inside MIP Solvers
• 13.5 User‐Defined MIP heuristics
• 13.6 Notes
• 13.7 Exercises
• 14 From Theory to Solutions
• 14.1 Introduction
• 14.2 Software for Solving Integer Programs
• 14.3 How Do We Find an Improved Formulation?
• 14.4 Multi‐item Single Machine Lot‐Sizing
• 14.5 A Multiplexer Assignment Problem
• 14.6 Integer Programming and Machine Learning*
• 14.7 Notes
• 14.8 Exercises
• References
• Index
• Integer Programming: 2nd Edition
• Solutions to Certain Exercises in IP Book
• Solutions to Certain Exercises in Chapter 1
• Solutions to Certain Exercises in Chapter 2
• Solutions to Certain Exercises in Chapter 3
• Solutions to Certain Exercises in Chapter 4
• Solutions to Certain Exercises in Chapter 5
• Solutions to Certain Exercises in Chapter 6
• Solutions to Certain Exercises in Chapter 7
• Solutions to Certain Exercises in Chapter 8
• Solutions to Certain Exercises in Chapter 9
• Solutions to Certain Exercises in Chapter 10
• Solutions to Certain Exercises in Chapter 11
• Solutions to Certain Exercises in Chapter 12
• Solutions to Certain Exercises in Chapter 13
• Solutions to Certain Exercises in Chapter 14
• End User License Agreement