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.
Since its inception more than fifty years ago, Mixed Integer Linear Programming (MILP) has become an indispensable tool in Operations Research. Enormous strides have been made both in the theoretical and computational issues arising in solving MILP problems. State-of-the-art commercial MILP solvers can now readily solve a wide range of industrial problems. However, in spite of MILP's success as a modeling tool, it is often useful to incorporate discrete variables into nonlinear models in order to better represent complex engineering and business optimization problems. This leads to Mixed Integer Nonlinear Programming (MINLP) problems. Recent use of MINLP includes applications in chemical engineering, environmental impact mitigation, design of pulse coders for audio amplification, layout design, logistics, machine-job assignment, network design, portfolio optimization, trim-loss optimization and water distribution systems design. Although a significant amount of research has been devoted to the development of practical algorithms for MINLP, there is still no universally effective black-box solver for MINLP. One reason for this contrast between MILP and MINLP solvers is that our theoretical understanding of the linear case vastly exceeds that of the nonlinear case. This research has significantly reduced the gap between MILP and MINLP theory, particularly concerning the fundamental theory of perhaps one of the most crucial technologies for the development of effective black-box solvers for MILP: cutting planes. The main accomplishments of this project have helped narrow the gap in our understanding of the interactions between nonlinear convex constraints and integrality requirements. The results obtained in this project can be classified into three groups: (1) Duality Results: We obtained a so-called subadditive dual for conic IPs, thus significantly generalizing the results known in the MILP setting. (2) Elementary Closures of Valid Inequalities: In a series of papers we studied split and Chvatal-Gomory (CG) cutting-planes. We were able to establish that the CG-closure of a compact convex set is a polytope. This result has important implication about the structure of these cutting-planes. (3) Cutting Plane Formulas: One reason for the success of cutting planes for MILP are the existence of simple formulas for extremely effective cuts. Unfortunately, almost no formulas for cutting planes for MINLP are known. In this project we were able to construct formulas for the natural extension of one of the most effective cutting planes for MILP: split cuts. Overall, the results obtained through this grant not only represent better understanding of fundamental questions arising in the context of convex MINLPs, but also push the limits of well-known results of MILP theory. The successful training of a PhD student was supported by this grant.
