Mixed Integer Optimization: New Cut Generation Paradigms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

After having served for decades as an amazingly versatile modeling tool, but one that could only solve practical problems of rather small sizes, mixed-integer optimization has undergone a true revolution in the last twenty years, greatly enhancing our ability to tackle practical problems in engineering, transportation, telecommunications, manufacturing, energy generation, finance, marketing and many other areas of economic activity. A key factor in this revolution was the incorporation of general-purpose cutting planes into the solvers, triggered by the lift-and-project cuts designed by the principal investigators in the early nineties under a previous NSF project, and the subsequent revival of Gomory's mixed integer cuts, also advocated by the principal investigators with previous NSF support. The objective of this research is to investigate new cutting plane paradigms meant to bring about another phase in the transformation of mixed-integer optimization solvers. The tools developed in this project are expected to have a broad impact and they should contribute to strengthening US technological leadership. This project will also contribute to the education and training of the PhD students involved in the research. Most of the cutting planes currently used in mixed-integer optimization solvers are valid for the classical corner relaxation, which can sometimes be rather weak. The principal investigators plan to develop new paradigms that will enable the construction of much richer families of cuts: generalized intersection cuts are produced in a non-recursive fashion from a family of points generated in advance; a general theory of cut-generating functions allows the generation of cuts through closed-form formulas. These and other theoretical results, aimed at producing stronger cuts, will be combined with computational investigations of their efficiency within the overall process of solving mixed-integer optimization problems. The tools used in this research will come from linear algebra such as projection and lifting, from convex analysis such as support functions and polarity, from geometry such as convex hull generation, from lattice theory such as maximal lattice-free convex sets and basis reduction, along with algorithmic techniques for efficient implementation. This project can be expected to advance the knowledge base in combinatorial and mixed-integer optimization, and to expand the algorithmic tool kit for mixed-integer optimization solvers. As in the past, software developed by the principal investigators and their PhD students will be open source and available on the web.