NSF Award: (Mixed) Integer and Combinatorial Optimization: New Convexification Techniques

A new NSF Award was recently given to Egon Balas on (Mixed) Integer and Combinatorial Optimization: New Convexification Techniques.

The objective of this research project is to investigate new ideas that could potentially further accelerate the revolution in integer programming. This project will investigate more efficient convexification techniques: a new cutting plane paradigm that generates a pool of points from which cuts can be produced, and a theory of cut-generating functions, both aimed at finding deeper cuts more efficiently. Integer programming 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 programming solvers are now close to a billion times faster than they were twenty years ago. Better integer programming algorithms (including their linear programming 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.


Progress in the ability to solve large-scale mixed integer linear programs will affect problem solving and improve 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 will contribute to technological excellence and strengthen US technological leadership.