Integer Programming

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.

LAURENCE A. WOLSEY is a mathematician working in the field of integer programming. He is a former president and research director of the Center for Operations Research and Econometrics (CORE) at UCLouvain in Belgium where he is Emeritus Professor of applied mathematics in the Engineering school.

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.4.1 The Shortest Path Problem

3.4.2 Maximum s–t Flow

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

vii

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.4.1 0–1 Knapsack

5.4.2 Integer Knapsack Problems

5.4.3 A Longest Path Extended Formulation

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.7.1 The Basic Mixed Integer Inequality

8.7.2 The Mixed Integer Rounding (MIR) Inequality

viii

8.7.3 The Gomory Mixed Integer Cut

8.7.4 Split 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.3.1 Cover Inequalities

9.3.2 Strengthening Cover Inequalities

9.3.3 Separation for Cover Inequalities

9.4 Mixed 0–1 Inequalities

9.4.1 Flow Cover Inequalities

9.4.2 Separation for Flow Cover Inequalities

9.5 The Optimal Subtour Problem

9.5.1 Separation for Generalized Subtour Constraints

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.7.1 Formulations

11.7.2 Solving the Subproblem

ix

11.7.3 The Load Formulation

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.4.1 Combining the Feasibility and Optimality Criteria.

12.4.2 The In-Out Approach

12.4.3 Using Facet-Defining Inequalities

12.5 Integer Subproblems: Basic Algorithms

12.5.1 Branching in the (x; ; y)-space.

12.5.2 Branching in (x; )-Space and No-good Cuts

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.3.1 Tabu Search 199

13.3.2 Simulated Annealing 200

13.3.3 Genetic Algorithms 202

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

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.