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

用于混合整数优化的新层次结构、割平面和算法

• 批准号: 1913294
• 负责人: Akshay Gupte
• 金额: $ 10万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-08-01 至 2020-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1913294&HistoricalAwards=false
• 关键词: New; Hierarchies; Cutting; Planes; Algorithms

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.

数学优化问题在科学和工程领域的许多应用中都出现。这些问题的很大一部分需要做出离散决策，其中一些未知数仅限于仅采用整数值。仍然需要迫切需要进一步提高解决混合整数问题的最先进的性能，尤其是当问题中的未知数通过非线性关系限制时。该研究项目开发了用于优化混合整数问题的新数学。通过实施新的和复杂的算法来解决这些问题，将可见整体影响。将开发一种辅助算法来帮助我们的主要算法，它也适用于决策理论，游戏理论和密码学中的优化。该算法将在基准问题上进行经验测试，并用于解决石油和天然气行业的应用以及统计学习中的基本问题，该问题广泛用于预测分析。该项目的研究将通过开发新的研究生课程来整合到课堂中，该课程在离散优化方面教授代数和组合方法。该奖项将通过研究为研究生培训提供支持。该项目在计算数学方面的主要研究目标是通过对可行整体问题（MIP）的可行区域（MIP）的可行区域来获得新颖的多面性放松。在某些单一顺序下的积分向量集。研究活动涉及开发有关切割平面，有效的不平等和MIP的多面体放松的丰富知识，MIPS的近似算法以及使用离散化方法有效地近似于具有多项式约束的MIP。因此，该项目将在计算代数，组合学和数学优化之间建立新的联系。我们使用单次订单生成切割平面的方法之一将概括并加强源自众所周知的拆分析取的切割平面。我们开发的理论并不明确取决于可行集合的代数表示，因此使其适用于所有类别的MIP，并且与许多明确取决于约束的现有研究非常不同的方法。反映了NSF的法定任务，并使用基金会的知识分子优点和更广泛的影响审查标准来评估值得支持。