Infinite-dimensional relaxations of mixed-integer optimization problems

University Of California-Davis, Davis CA

Investigators

Abstract

Mixed-integer linear optimization is a mature discipline of mathematical optimization and a key technology of Operations Research and Mathematical Analytics. Key ingredients of the state-of-the-art solver technology are so-called cutting planes. Strong cutting planes for combinatorial optimization problems (e.g., the TSP) arise from sophisticated studies of the polyhedral combinatorics of convex hulls. In contrast, the state-of-the-art solvers for mixed-integer optimization problems use cuts such as the Gomory's mixed-integer cut, which are derived by integer rounding principles from a single row of the simplex tableau. The performance of cutting planes has stagnated since the computational breakthroughs of the late 1990s, early 2000s. To meet the challenges of ever more demanding applications, it is desired to make use of information from several rows of the tableau. Finding such "effective multi-row cuts" is the most important open question in mixed-integer linear optimization. The PI proposes to study Gomory Johnson's (1972) k-row infinite group problem. This problem is infinite-dimensional; its convex geometry is notoriously hard to study. Finding a characterization of extreme functions corresponding to facet-defining inequalities of polyhedral combinatorics) even for k = 1 had eluded researchers for the past four decades. The methods used in the breakthrough algorithmic classification by the PI and coauthors of the 1-row rational piecewise linear extreme functions show a route for further work: The arithmetic aspect of the problem (neglected in the literature) leads to the study of reflection groups and their action. The arithmetic interacts closely with the discrete geometry of the problem, where certain periodic polyhedral complexes arise. On the analytic side of the problem, one needs to consider solutions to functional equations of several variables that generalize the one studied by Cauchy and its generalizations by Aczel, Baker, Chung. On the computational side, besides the development of new numerically stable cutting plane procedures, computer-based search will be employed. The revival of industrial manufacturing in America is closely tied to the field of Analytics, which is the science of making the best decisions in manufacturing and business processes, on the basis of the ever-growing amounts of available data. Mathematical Optimization is one of the key hard sciences of Analytics. It provides powerful computational technologies (optimization algorithms and software). One such technology are so-called "mixed-integer linear optimization solvers," which are used by thousands of Analytics experts in all of our industries, including manufacturing, biotechnology, and sustainable infrastructure. However, one key component in today's mixed-integer linear optimization software has not kept up with the demand to use more and more data in order to come to better decisions, and thus to increase the dimension of the optimization problem: Today's mixed-integer "cutting plane separators" still only look at one row of an array of data called the "simplex tableau" at a time. As the number of rows grows, this technique is becoming weaker and weaker. Researchers have long sought to find effective "multi-row cutting plane separators". The PI proposes to study an innovative approach, using the "k-row infinite group problem," which will extend his recent breakthrough work on this topic with students and collaborators. This will lead to new mathematical insights, more efficient algorithms and new, more powerful optimization software. This project also has a strong educational impact. The PI plans to train several undergraduate and graduate students in this research area. One component of the training will be to create new course material on the topics of this proposal, and to use it for new classes for undergraduate and graduate students. The second component of the training consists of direct involvement of students in this research project, involving theoretical work, computer experimentation, and software implementation, all of which lead to undergraduate and graduate theses. All of this will prepare the students for far-reaching careers as experts in Mathematical Analytics, who are able to use the most cutting edge optimization technology.