Global Optimization of Mixed Integer Nonlinear Programs:
Theory, Algorithms and Computations

Interest in constrained optimization originated with the simple linear programming model since it was practical and perhaps the only computationally tractable model at the time. Advances in computing technology have altered and continue to rapidly change this situation. Meanwhile, the assumption of linearity has been found to be restrictive in modeling a variety of applications in economics, finance, business, communication, engineering design, computational biology, and other areas. As a result, researchers seek efficient methods to solve nonlinear models.

Initial attempts at solving nonlinear programs concentrated on the development of local optimization methods guaranteeing globality under the assumption of convexity. However, many optimization problems of practical relevance exhibit multiple local minima, demanding the use of global optimization methods. In my dissertation, under the guidance of Prof. Nick Sahinidis, I develop, analyze, implement and apply global optimization algorithms to solve mixed integer nonlinear programming problems. There are currently few solution strategies explicitly addressing mixed integer nonlinear programs and implementations are virtually non-existent.

I made various theoretical and algorithmic advances in my thesis. More specifically:

• I developed the first constructive technique for characterizing convex envelopes of nonlinear functions. Demonstrating the technique, I derived a new semidefinite relaxation for fractional programs. In the process, I introduced the concept of convex extensions and through its study revealed many interesting properties of convexification schemes.
• I developed a new theoretical framework for range-reduction and identified its connections with Lagrangian outer-approximation. Within the developed framework, I provided a unified treatment of existing and several new domain reduction techniques.
• I developed a finite branch and bound algorithm for two stage stochastic integer programs where prior approaches were either convergent only in limit (i.e, infinite) or resorted to explicit enumeration.

The above advancements have been placed in an easily usable computational framework. Through computational experience, I demonstrated that my implementation can now routinely solve problems previously not amenable to optimization techniques. In particular:

• I designed and implemented a branch and bound based mixed integer nonlinear programming algorithm (BARON-NLP). My web-portal for BARON-NLP provides a service to the optimization community and acts as the solver's test-bed. Last year, over 3500 problems were submitted to the online solver by 95 different research groups.
• I completely characterized the feasible space of a refrigerant design problem proposed 15 years ago revealing all the 44 candidate refrigerants that meet the design specifications.
• I developed global optimization techniques and software for certain benchmark problems in stochastic decision making, pooling and blending problems in the petrochemical industry, and restaurant location problems. My results provided new solutions and/or improved computational performance with respect to earlier approaches.

Email Address: mtawarma@mgmt.purdue.edu
URL: http://web.ics.purdue.edu/~mtawarma/