Collaborative Research: Fundamentals of Convex Mixed Integer Nonlinear Programming

凸混合整数非线性规划（MINLP）为建模多种复杂的现实工程和商业优化问题提供了多种可能性。然而，目前还没有像混合整数线性规划（MILP）那样普遍有效的通用凸MINLP求解器。本项目的研究目标是将MILP中已知的以下关键结果的范围扩大到凸MINLP的更一般领域：(i)推广可行解凸壳的表示定理。（ii）研究凸minlp的值函数性质（如次可加性）。（iii）研究构建强对偶的可能性。（iv）分析使用次加性有效不等式作为切割平面的可能性。(v)检查基本切割面闭包的性质，如chval - gomory闭包和Split闭包。在MILP的情况下，上述结果是切割平面理论的核心，这是成功求解的关键因素。此外，理解价值函数和强对偶在灵敏度分析和随机版本的MILP的背景下是重要的。因此，如果该项目成功，该提案的结果将有助于在设计实用的minlp算法方面产生积极影响。特别是，由于上面提到的许多问题都与表示和切割平面有关，积极的结果应该有助于开发更快的凸MINLP分支切割算法。

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.