Integer Programming

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 Non-Bipartite 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 NP and P 6.3 Polynomial Reduction and the Class NPC 6.4 Consequences of P = NP or P 8= NP 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 and Variable Fixing 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 Master Linear Program by Column Generation 11.4 Solving the Column Generation Subproblem 11.4 Solving the IP Master Integer Program: Branch-and-Price 11.5 Problem Variants 11.5.1 Handling Multiple Subproblems 11.5.2 Partitioning/Packing Problems with Additional Variables 11.5.3 Partitioning/Packing Problems with Identical Subsets 11.6 Computational Issues 11.7 Branch-and-Cut-and-Price: Capacitated Vehicle Routing 11.8 Notes 11.9 Exercises 12. Benders' Algorithm 12.1 Introduction 12.2 Benders' Reformulation 12.3 MIPs with Block Diagonal Structure 12.4 Solving the LP Separation Problems 12.5 Integer Subproblems: Basic Algorithms 12.6 Notes 12.7 Exercises 13 Heuristic Algorithms 13.1 Introduction 195 13.2 Greedy and Local Search Revisited 196 13.3 Improved Local Search Heuristics 199 13.4 Heuristics inside MIP Solvers 13.5 User-designed MIP Heuristics 13.6 Notes 13.7 Exercises 14 From Theory to Solutions 14.1 Introduction 14.2 Software for Solving Mixed 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