权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Infinite-dimensional relaxations of mixed-integer optimization problems

混合整数优化问题的无限维松弛

基本信息

批准号：
1320051
负责人：
Matthias Koeppe
金额：
$ 21.99万
依托单位：
University of California-Davis
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2013
资助国家：
美国
起止时间：
2013-08-15 至 2017-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320051&HistoricalAwards=false
关键词：
Infinite dimensional relaxations mixed integer

项目摘要

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.

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