Collaborative Research: Fundamentals of Convex Mixed Integer Nonlinear Programming

University Of Pittsburgh, Pittsburgh PA

Investigators

Abstract

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.