Mixed Integer Nonlinear Programs: Theory, Algorithms and Applications

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Tawarmalani, Mohit

Contributors dc:contributor

• Sahinidis, Nikolaos V.

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI3023212

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/87075