New Hierarchies, Cutting Planes, and Algorithms for Mixed Integer Optimization

数学优化问题在科学和工程的各个领域都有广泛的应用。这些问题中的很大一部分需要做出离散的决策，其中一些未知数被限制为只能取整数值。迫切需要进一步提高解决混合整数问题的性能，特别是当问题中的未知数受到非线性关系的约束时。本研究项目发展了优化混合整数问题的新数学。通过实施新的复杂算法来解决这些问题，整体影响将是可见的。我们将开发一种辅助算法来辅助我们的主要算法，它也将适用于决策理论、博弈论和密码学中的优化。这些算法将在基准问题上进行实证测试，并用于解决石油和天然气行业的应用程序以及广泛用于预测分析的统计学习中的基本问题。这个项目的研究将通过开发一门新的研究生课程整合到课堂上，该课程教授离散优化中的代数和组合方法。该奖项将通过研究为研究生培训提供支持。本课题在计算数学领域的主要研究目标是通过对在某些单项式排序下由有序的积分向量集合产生的离散可行域的创新解释，推导出混合整数问题可行域的新多面体松弛。研究活动包括开发丰富的知识体系，包括切割平面、有效不等式、MIPs的多面体松弛、MIPs的逼近算法，以及使用离散化方法有效地逼近多项式约束下的MIPs。因此，这个项目将在计算代数、组合学和数学优化之间建立新的联系。我们的一种利用单阶生成切割平面的方法，推广并加强了由众所周知的分裂析断导出的切割平面。我们发展的理论并不明确地依赖于可行集的代数表示，因此使其适用于所有类别的MIP，并且与许多明确依赖于约束的线性的现有研究提出了非常不同的方法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Mathematical optimization problems arise in many applications in diverse fields in science and engineering. A large portion of these problems require discrete decisions to be made, where some of the unknowns are restricted to take only integer values. There continues to be a pressing need to further improve the performance of the state-of-the-art for solving mixed integer problems, especially when the unknowns in the problem are constrained through nonlinear relationships. This research project develops new mathematics for optimizing mixed integer problems. The overall impact will be visible through the implementation of new and sophisticated algorithms for solving these problems. An auxiliary algorithm will be developed to aid our main algorithm and it will also be applicable to optimization in decision theory, game theory, and cryptography. The algorithms will be empirically tested on benchmark problems, and used to solve an application in oil and gas industry and a fundamental problem in statistical learning that is widely-used for predictive analytics. Research from this project will be integrated into classroom through the development of a new graduate course that teaches algebraic and combinatorial methods in discrete optimization. The award will provide support for graduate student training through research.The primary research objective of this project in computational mathematics is to derive novel polyhedral relaxations for the feasible regions of mixed integer problems (MIPs) through an innovative interpretation of discrete feasible regions arising from ordered sets of integral vectors under some monomial ordering. The research activities involve developing a rich body of knowledge about cutting planes, valid inequalities, and polyhedral relaxations for MIPs, approximation algorithms for MIPs, and using discretization methods to efficiently approximate MIPs with polynomial constraints. Thus, this project will establish new connections between computational algebra, combinatorics, and mathematical optimization. One of our methods for generating cutting planes using a monomial order generalizes and strengthens the cutting planes derived from the well-known split disjunctions. The theory we develop does not depend explicitly on the algebraic representation of the feasible set, therefore making it applicable to all classes of MIP and presenting a very different approach than many of the existing studies that explicitly depend on the linearity of the constraints.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.