Integer Programming: 271

Preface
Contents
1 Getting Started
	1.1 Integer Programming
	1.2 Methods for Solving Integer Programs
		1.2.1 The Branch-and-Bound Method
		1.2.2 The Cutting Plane Method
		1.2.3 The Branch-and-Cut Method
	1.3 Complexity
		1.3.1 Problems, Instances, Encoding Size
		1.3.2 Polynomial Algorithm
		1.3.3 Complexity Class NP
	1.4 Convex Hulls and Perfect Formulations
		1.4.1 Example: A Two-Dimensional Mixed Integer Set
		1.4.2 Example: A Two-Dimensional Pure Integer Set
	1.5 Connections to Number Theory
		1.5.1 The Greatest Common Divisor
		1.5.2 Integral Solutions to Systems of Linear Equations
	1.6 Further Readings
	1.7 Exercises
2 Integer Programming Models
	2.1 The Knapsack Problem
	2.2 Comparing Formulations
	2.3 Cutting Stock: Formulations with Many Variables
	2.4 Packing, Covering, Partitioning
		2.4.1 Set Packing and Stable Sets
		2.4.2 Strengthening Set Packing Formulations
		2.4.3 Set Covering and Transversals
		2.4.4 Set Covering on Graphs: Many Constraints
		2.4.5 Set Covering with Many Variables: Crew Scheduling
		2.4.6 Covering Steiner Triples
	2.5 Generalized Set Covering: The Satisfiability Problem
	2.6 The Sudoku Game
	2.7 The Traveling Salesman Problem
	2.8 The Generalized Assignment Problem
	2.9 The Mixing Set
	2.10 Modeling Fixed Charges
		2.10.1 Facility Location
		2.10.2 Network Design
	2.11 Modeling Disjunctions
	2.12 The Quadratic Assignment Problemand Fortet\'s Linearization
	2.13 Further Readings
	2.14 Exercises
3 Linear Inequalities and Polyhedra
	3.1 Fourier Elimination
	3.2 Farkas\' Lemma
	3.3 Linear Programming
	3.4 Affine, Convex, and Conic Combinations
		3.4.1 Linear Combinations, Linear Spaces
		3.4.2 Affine Combinations, Affine Spaces
		3.4.3 Convex Combinations, Convex Sets
		3.4.4 Conic Combinations, Convex Cones
	3.5 Polyhedra and the Theorem of Minkowski–Weyl
		3.5.1 Minkowski–Weyl Theorem for Polyhedral Cones
		3.5.2 Minkowski–Weyl Theorem for Polyhedra
	3.6 Lineality Space and Recession Cone
	3.7 Implicit Equalities, Affine Hull, and Dimension
	3.8 Faces
	3.9 Minimal Representation and Facets
	3.10 Minimal Faces
	3.11 Edges and Extreme Rays
	3.12 Decomposition Theorem for Polyhedra
	3.13 Encoding Size of Vertices, Extreme Rays, and Facets
	3.14 Carathéodory\'s Theorem
	3.15 Projections
	3.16 Polarity
	3.17 Further Readings
	3.18 Exercises
4 Perfect Formulations
	4.1 Properties of Integral Polyhedra
	4.2 Total Unimodularity
	4.3 Networks
		4.3.1 Circulations
		4.3.2 Shortest Paths
		4.3.3 Maximum Flow and Minimum Cut
	4.4 Matchings in Graphs
		4.4.1 Augmenting Paths
		4.4.2 Cardinality Bipartite Matchings
		4.4.3 Minimum Weight Perfect Matchingsin Bipartite Graphs
		4.4.4 The Matching Polytope
	4.5 Spanning Trees
	4.6 Total Dual Integrality
	4.7 Submodular Polyhedra
	4.8 The Fundamental Theoremof Integer Programming
		4.8.1 An Example: The Mixing Set
		4.8.2 Mixed Integer Linear Programming is in NP
		4.8.3 Polynomial Encoding of the Facets of the Integer Hull
	4.9 Union of Polyhedra
		4.9.1 Example: Modeling Disjunctions
		4.9.2 Example: All the Even Subsets of a Set
		4.9.3 Mixed Integer Linear Representability
	4.10 The Size of a Smallest Perfect Formulation
		4.10.1 Rectangle Covering Bound
		4.10.2 An Exponential Lower-Bound for the Cut Polytope
		4.10.3 An Exponential Lower-Bound for theMatching Polytope
	4.11 Further Readings
	4.12 Exercises
5 Split and Gomory Inequalities
	5.1 Split Inequalities
		5.1.1 Inequality Description of the Split Closure
		5.1.2 Polyhedrality of the Split Closure
		5.1.3 Split Rank
		5.1.4 Gomory\'s Mixed Integer Inequalities
		5.1.5 Mixed Integer Rounding Inequalities
	5.2 Chvátal Inequalities
		5.2.1 The Chvátal Closure of a Pure Integer Linear Set
		5.2.2 Chvátal Rank
		5.2.3 Chvátal Inequalities for Other Formsof the Linear System
		5.2.4 Gomory\'s Fractional Cuts
		5.2.5 Gomory\'s Lexicographic Method for PureInteger Programs
	5.3 Gomory\'s Mixed Integer Cuts
	5.4 Lift-and-Project
		5.4.1 Lift-and-Project Rank for Mixed 0,1Linear Programs
		5.4.2 A Finite Cutting Plane Algorithm for Mixed 0,1Linear Programming
	5.5 Further Readings
	5.6 Exercises
6 Intersection Cuts and Corner Polyhedra
	6.1 Corner Polyhedron
	6.2 Intersection Cuts
		6.2.1 The Gauge Function
		6.2.2 Maximal Lattice-Free Convex Sets
	6.3 Infinite Relaxations
		6.3.1 Pure Integer Infinite Relaxation
			Extreme Valid Functions and the Two-Slope Theorem
		6.3.2 Continuous Infinite Relaxation
		6.3.3 The Mixed Integer Infinite Relaxation
		6.3.4 Trivial and Unique Liftings
	6.4 Further Readings
	6.5 Exercises
7 Valid Inequalities for Structured Integer Programs
	7.1 Cover Inequalities for the 0,1 Knapsack Problem
	7.2 Lifting
		7.2.1 Lifting Minimal Cover Inequalities
		7.2.2 Lifting Functions, Superadditivity, and SequenceIndependent Lifting
		7.2.3 Sequence Independent Lifting for MinimalCover Inequalities
	7.3 Flow Cover Inequalities
	7.4 Faces of the Symmetric Traveling Salesman Polytope
		7.4.1 Separation of Subtour Elimination Constraints
		7.4.2 Comb Inequalities
		7.4.3 Local Cuts
	7.5 Equivalence Between Optimizationand Separation
	7.6 Further Readings
	7.7 Exercises
8 Reformulations and Relaxations
	8.1 Lagrangian Relaxation
		8.1.1 Examples
			Uncapacitated Facility Location
			Traveling Salesman Problem
		8.1.2 Subgradient Algorithm
	8.2 Dantzig–Wolfe Reformulation
		Relation with the Lagrangian Dual
		8.2.1 Problems with Block Diagonal Structure
		8.2.2 Column Generation
		8.2.3 Branch-and-Price
	8.3 Benders Decomposition
	8.4 Further Readings
		Lagrangian Relaxation
		Cutting Stock
		Dantzig–Wolfe Reformulation and Column Generation
		Benders Reformulation
	8.5 Exercises
9 Enumeration
	9.1 Integer Programming in Fixed Dimension
		9.1.1 Basis Reduction
		9.1.2 The Flatness Theorem and Rounding Polytopes
		9.1.3 Lenstra\'s Algorithm
	9.2 Implementing Branch-and-Cut
	9.3 Dealing with Symmetries
		Isomorphism Pruning
		Orbital Fixing
	9.4 Further Readings
		Integer Programming in Fixed Dimension
		Computational Aspects of Branch-and-Bound
		Dealing with Symmetry
	9.5 Exercises
10 Semidefinite Bounds
	10.1 Semidefinite Relaxations
	10.2 Two Applications in Combinatorial Optimization
		10.2.1 The Max-Cut Problem
		10.2.2 The Stable Set Problem
	10.3 The Lovász–Schrijver Relaxation
		10.3.1 Semidefinite Versus Linear Relaxations
		10.3.2 Connection with Lift-and-Project
		10.3.3 Iterating the Lovász–Schrijver Procedure
	10.4 The Sherali–Adams and Lasserre Hierarchies
		10.4.1 The Sherali–Adams Hierarchy
		10.4.2 The Lasserre Hierarchy
			An Application to the Stable Set Problem
	10.5 Further Readings
	10.6 Exercises
Bibliography
Index