Collaborative Research: Fundamentals of Convex Mixed Integer Nonlinear Programming

凸混合整数非线性规划(MINLP)为许多复杂的现实世界工程和商业优化问题的建模提供了许多可能性。然而，目前还没有像混合整数线性规划(MILP)那样通用的通用凸MINLP求解器。本项目的研究目的是将MILP中已知的下列主要结果推广到更一般的凸MINLP区域：(I)推广可行解的凸壳的表示定理。(Ii)研究了凸MINLP的值函数的性质(如次可加性)。(3)研究构造强对偶的可能性。(4)分析了次可加有效不等式作为割平面的可能性。(V)研究初等割平面闭包的性质，如Chvtal-Gomory闭包和分裂闭包。在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.