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.
Integer optimization has experienced a revolution in the last two decades that has greatly advanced our ability to solve practical problems in engineering, manufacturing, transportation, telecommunication, finance, marketing and many other areas of economic activity. According to recently performed extensive testing, integer optimization solvers are now close to a billion times faster than they were twenty years ago. Better integer optimization algorithms (including their linear optimization components) account for a speedup of about half a million times, the rest of the improvement (by a factor of about 1600) coming from faster computers. A key element of this transformation was a breakthrough in the use of cutting planes in the early nineties, including the design of the lift-and-project cuts and the ensuing revival of the Gomory mixed integer cuts, two projects carried out by the principal investigators with previous NSF support. Under NSF grant CMMI 1024554, the principal investigators, Egon Balas and Gerard Cornuejols, continued improving the state-of-the-art of integer and combinatorial optimization by developing new convexification techniques: stronger cutting planes, generated more efficiently and used in novel ways. Progress in our ability to solve large-scale mixed integer linear optimization problems improves efficiency of operations in an extremely broad range of activities that include industrial production, supply chain management, logistics, transportation, electricity production, airport operations, telecommunication networks, health care applications such as scheduling intensive care units and determining radiation dosage, combinatorial auctions, finance and economics. The widespread impact of tools developed in this project contributes to technological excellence and strengthens US technological leadership.
