Integer programming

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