Mixed integer nonlinear programs: Theory, algorithms and applications.

摘要

Interest in constrained optimization originated with the linear programming model since it was practical and perhaps the only computationally tractable model at the time. It was, however, soon realized that the assumption of linearity is too restrictive for modeling application problems in finance, business, engineering, sciences, and many other areas. Initial attempts at solving the resulting nonlinear programs concentrated on the development of local optimization methods. However, the developed algorithms proved inadequate for solving a plethora of practically motivated optimization problems which exhibit multiple local minima. Consequently, researchers felt the need for global optimization techniques.; This dissertation develops an efficient solution strategy for finding global optima of continuous, integer, and mixed integer nonlinear programs. The main contributions of this thesis are: (1) We develop the first constructive technique for characterizing convex envelopes of nonlinear functions. Demonstrating the technique, we derive a semidefinite relaxation for fractional programs. In the process, we introduce the concept of convex extensions, study its convexification properties, and apply it to develop tight relaxations for hyperbolic programs and pooling/blending problems. (2) We develop a theoretical framework for range-reduction and provide a unified treatment of existing and new domain reduction techniques. (3) We develop a finite algorithm for two stage stochastic integer programs where earlier approaches were either convergent only in limit (i.e., infinite) or resorted to explicit enumeration. (4) We provide computational experience to demonstrate that our implementation of the proposed algorithms (BARON-NLP) can routinely solve problems previously not amenable to optimization techniques. We characterize the feasible space of a refrigerant design problem proposed 15 years ago and provide new solutions and/or improved computational results with respect to earlier approaches on benchmark problems in stochastic decision making, pooling and blending problems in the petrochemical industry, and restaurant location problems.