A PRACTICAL GUIDE TO OPTIMIZATION PROBLEMS WITH DISCRETE OR INTEGER VARIABLES, REVISED AND UPDATED
The revised second edition of Integer Programming explains in clear and simple terms how to construct custom-made algorithms or use existing commercial software to obtain optimal or near-optimal solutions for a variety of real-world problems. The second edition also includes information on the remarkable progress in the development of mixed integer programming solvers in the 22 years since the first edition of the book appeared. The updated text includes information on the most recent developments in the field such as the much improved preprocessing/presolving and the many new ideas for primal heuristics included in the solvers. The result has been a speed-up of several orders of magnitude. The other major change reflected in the text is the widespread use of decomposition algorithms, in particular column generation (branch-(cut)-and-price) and Benders’ decomposition. The revised second edition:
- Contains new developments on column generation
- Offers a new chapter on Benders’ algorithm
- Includes expanded information on preprocessing, heuristics, and branch-and-cut
- Presents several basic and extended formulations, for example for fixed cost
- network flows
- Also touches on and briefly introduces topics such as non-bipartite matching, the complexity of extended formulations or a good linear program for the implementation of lift-and-project
Written for students of integer/mathematical programming in operations research, mathematics, engineering, or computer science, Integer Programming offers an updated edition of the basic text that reflects the most recent developments in the field.
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 ̸= 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
