Collaborative Research: Fundamentals of Convex Mixed Integer Nonlinear Programming

协作研究：凸混合整数非线性规划基础

• 批准号: 1030662
• 负责人: Juan Pablo Vielma
• 金额: $ 20万
• 依托单位: University of Pittsburgh
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1030662&HistoricalAwards=false
• 关键词: Collaborative; Research; Fundamentals; Convex; Mixed

Convex Mixed Integer Nonlinear Programming (MINLP) presents many possibilities for modeling many classes of complex real world engineering and business optimization problems. However, there are no universally effective general purpose convex MINLP solvers such as those available for Mixed Integer Linear Programming (MILP). The research objective of this project is to broaden the scope of the following key results known for MILP to the more general domain of convex MINLP: (i) Generalize representation theorems for the convex hull of feasible solutions. (ii) Study properties of the value functions (such as subadditivity) of convex MINLPs. (iii) Investigate the possibility of constructing strong duals. (iv) Analyze the potential of using subadditive valid inequalities as cutting planes. (v) Examine the properties of elementary cutting plane closures such as Chvatal-Gomory and Split closure. In the case of MILP, the above mentioned results are central to cutting plane theory, a key ingredient in successful solvers. Moreover, understanding value functions and strong duals are important in the context of sensitivity analysis and stochastic versions of MILP. Therefore, if this project is successful, the results from this proposal will help in making a positive impact in designing practical algorithms for MINLPs. In particular, since many of the questions mentioned above are related to representation and cutting planes, positive results should help the development of faster branch-and-cut algorithms for convex MINLP.

凸混合非线性规划（MINLP）为建模许多类复杂的真实的世界工程和商业优化问题提供了许多可能性。然而，没有普遍有效的通用凸MINLP求解器，如那些可用于混合线性规划（MILP）。本项目的研究目标是将MILP的以下主要结果扩展到更一般的凸MINLP领域：（i）推广可行解的凸船体的表示定理。(ii)研究凸MINLP的值函数的性质（如次可加性）。(iii)探讨构建强有力的可持续发展体系的可能性。(iv)分析次可加有效不等式作为割平面的可能性。(v)检查基本割平面闭包的性质，如Chvatal-Gomory闭包和Split闭包。 在MILP的情况下，上述结果是中央切割平面理论，在成功的求解器的关键成分。此外，理解价值函数和强可检验性在敏感性分析和随机版本的MILP中是重要的。因此，如果这个项目是成功的，从这个建议的结果将有助于在设计实用的算法MINLP的积极影响。特别是，由于上述许多问题都与表示和切割平面，积极的结果应该有助于开发更快的分支和切割算法凸MINLP。