Infinite-dimensional relaxations of mixed-integer optimization problems

混合整数线性优化是一门成熟的数学优化学科，是运筹学和数学分析的一项关键技术。最先进的求解器技术的关键成分是所谓的切割平面。组合优化问题(如TSP)的强割平面源于对凸壳的多面体组合学的复杂研究。相比之下，最先进的混合整数优化问题的求解器使用诸如Gomory的混合整数切割之类的切割，这些切割是通过整数舍入原则从单纯形Tableau的单行中派生出来的。自20世纪90年代末、21世纪初的计算突破以来，切割飞机的性能一直停滞不前。为了应对要求越来越高的应用程序的挑战，需要利用画面中几行的信息。寻找这种“有效的多行割集”是混合整数线性优化中最重要的公开问题。PI建议研究Gomory Johnson(1972)的k行无限群问题。这个问题是无限维的；它的凸几何学是出了名的难研究。在过去的四十年里，即使对于k=1，也找不到与多面体组合数学的刻面定义不等式相对应的极值函数的特征。PI和合著者在1行有理分段线性极值函数的突破性算法分类中使用的方法为进一步的工作指明了道路：这个问题的算术方面(在文献中被忽略)导致了对反射群及其作用的研究。该算法与问题的离散几何密切相关，在离散几何中出现了某些周期多面体复合体。在问题的分析方面，需要考虑多元函数方程的解，这些方程推广了柯西研究的方程及其Aczel，Baker，Chung的推广。在计算方面，除了开发新的数字稳定的切割平面程序外，还将采用基于计算机的搜索。美国工业制造业的复兴与分析领域密切相关，分析领域是一门根据不断增长的可用数据在制造和商业流程中做出最佳决策的科学。数学最优化是分析学的一门重要的硬科学。它提供强大的计算技术(优化算法和软件)。其中一种技术是所谓的“混合整数线性优化求解器”，我们所有行业的数千名Analytics专家都在使用这种技术，包括制造业、生物技术和可持续基础设施。然而，今天的混合整数线性优化软件中的一个关键组件没有跟上需求，即为了做出更好的决策而使用越来越多的数据，从而增加了优化问题的维度：今天的混合整数“切割平面分隔符”一次仍然只查看一组数据中的一行，称为“单纯形表”。随着行数的增加，这种技术变得越来越弱。长期以来，研究人员一直在寻找有效的“多排切面分离器”。PI建议研究一种创新的方法，使用“k行无限群问题”，这将扩展他最近在这一主题上的突破性工作，与学生和合作者。这将带来新的数学见解、更有效的算法和新的、更强大的优化软件。这个项目也有很强的教育影响。PI计划在这一研究领域培养几名本科生和研究生。培训的一个组成部分将是就本提案的主题创建新的课程材料，并将其用于本科生和研究生的新课程。培训的第二部分包括让学生直接参与这个研究项目，包括理论工作、计算机实验和软件实施，所有这些都会导致本科生和研究生的论文。所有这些都将为学生作为数学分析专家的深远职业生涯做好准备，他们能够使用最尖端的优化技术。

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.