Integer and Combinatorial Optimization: Intersection Cuts from Multiple Rows

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The central objective of this project is to accelerate the pace of the revolution in the state-of-the-art of integer programming that took place over the last 15 years. Until the early 1990's, integer programming, a universal tool for modeling real-world situations characterized by the absence of convexity, smoothness, continuity, could only solve very small problem instances. Over the last 15 years, due partly to the successful adaptation of new convexification procedures, the reach of integer programming has been vastly extended so that today it can cope with problems involving thousands of variables and constraints. This project is aimed at developing new and more efficient convexification techniques in the form of improved lift-and-project cuts derived directly from the simplex tableau, intersection cuts from multiple rows or multiple term disjunctions, cuts obtained by iterative disjunctive modularization, pure integer cuts generated lexicographically, and others. The techniques to be developed promise to yield cuts that are not only deeper, but more diverse and stable, thereby tightening the linear relaxation of the mixed integer programs at hand, and reducing the size of the search tree generated in the process. This is expected to increase by an order of magnitude the size of the instances solvable in useful time and thereby to extend the sphere of solvable problems to new types of mixed integer programs that arise in supply chain management, industrial scheduling and other real-world environments.