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

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

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.