Integer Programming

In a linear programming (LP) problem, we wish to minimize (or maximize) a linear function of a vector of variables subject to linear equality and inequality constraints on the variables. In (linear) integer programming, some or all of the variables are required to take on only integer values. Integer programming extends linear programming significantly by making it possible to model binary or discrete choices. Integer programming problems arise in practice in many areas of operations research.

Integer programming problems are considerably harder to solve, however, than linear programming problems — both in theory and in practice. In theory, linear programming problems can be solved in polynomial time, while integer programming is NP-Hard. Existing algorithms for integer programming have worst case exponential time complexity. While linear programming problems with hundreds of thousands and even millions of variables can be solved by modern linear programming solvers, integer programming problems with a few thousand variables may easily confound integer programming codes.

We can easily obtain a lower bound on the optimal value of an integer programming problem by relaxing the integrality constraints and solving the resulting LP. Although the optimal value of this LP is a lower bound on the minimum of the original integer programming problem, the optimal solution will typically have some non-integer components. In a strategy called branch-and-bound, a tree search is used to divide the set of integer solutions into subsets. Leaf nodes of the tree either result in integer solutions or have lower bounds that have been dominated by some known integer solution.

Another approach to integer programming problems is to reformulate the integer programming problem as a linear programming problem over the convex hull of the feasible integer solutions. Any optimal solution to this linear programming problem will necessarily satisfy the linear constraints. Furthermore, it is always possible to find an optimal solution which is also an extreme point of the polyhedron and thus an integer solution. The convex hull of the integer feasible solutions would typically involve an exponential number of inequalities, but in practice, we can add violated inequalities to the LP relaxation until an optimal integer solution is obtained. The inequalities added to the LP formulation are referred to as cuts. This cutting plane approach to integer programming can be combined with branch-and-bound in a branch-and-cut algorithm.

Integer Programming begins by introducing the subject and giving several examples of integer programming problems. This is followed by chapters on the theory of linear inequalities and polyhedra, integral polyhedra, Gomory-Chvatal cuts, and families of valid inequalities for various problems. The book ends with chapters on decomposition strategies, branch-and-cut, and semidefinite programming relaxations of integer programming problems.

This book would be suitable for a graduate level course on the mathematics of cutting plane methods. Students would need to have a strong background in linear algebra and linear programming. This book might also be of interest as a reference for researchers working in this area. A natural comparison are the books listed below, which are more like encyclopedic references on combinatorial optimization and integer programming. This book offers a more focused presentation that makes it better suited for use as a textbook.

References

[1] Alexander Schrijver. Combinatorial Optimization: Algorithms and Efficiency (3 volumes.) Springer Verlag, Heidelberg, 2003.

[2] Laurence A. Wolsey and George L. Nemhauser. Integer and Combinatorial Optimization. Wiley, New York, 1988.

Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.