Mixed integer programming approaches for nonlinear and stochastic programming

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/29624

Title: Mixed integer programming approaches for nonlinear and stochastic programming
Author: Vielma Centeno, Juan Pablo
Abstract: In this thesis we study how to solve some nonconvex optimization problems by using methods that capitalize on the success of Linear Programming (LP) based solvers for Mixed Integer Linear Programming (MILP). A common aspect of our solution approaches is the use, development and analysis of small but strong extended LP/MILP formulations and approximations. In the first part of this work we develop an LP based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a lifted polyhedral relaxation of conic quadratic constraints by Ben-Tal and Nemirovski. We test the algorithm on a series of portfolio optimization problems and show that it provides a significant computational advantage. In the second part we study the modeling of a class of disjunctive constraints with a logarithmic number of variables. For specially structured disjunctive constraints we give sufficient conditions for constructing MILP formulations with a number of binary variables and extra constraints that is logarithmic in the number of terms of the disjunction. Using these conditions we introduce formulations with these characteristics for SOS1, SOS2 constraints and piecewise linear functions. We present computational results showing that they can significantly outperform other MILP formulations. In the third part we study the modeling of non-convex piecewise linear functions as MILPs. We review several new and existing MILP formulations for continuous piecewise linear functions with special attention paid to multivariate non-separable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study the extension of these formulations to lower semicontinuous piecewise linear functions. Finally, in the fourth part we study the strength of MILP formulations for LPs with Probabilistic Constraints. We first study the strength of existing MILP formulations that only considers one row of the probabilistic constraint at a time. We then introduce an extended formulation that considers more than one row of the constraint at a time and use it to computationally compare the relative strength between formulations that consider one and two rows at a time.
Type: Dissertation
URI: http://hdl.handle.net/1853/29624
Date: 2009-07-06
Publisher: Georgia Institute of Technology
Subject: Mixed integer programming
Stochastic programming
Mathematical optimization
Nonconvex programming
Department: Industrial and Systems Engineering
Advisor: Committee Chair: Nemhauser, George; Committee Co-Chair: Ahmed, Shabbir; Committee Member: Bill Cook; Committee Member: Gu, Zonghao; Committee Member: Johnson, Ellis
Degree: Ph.D.

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
vielma_centeno_juan_pablo_200908_phd.pdf 1.705Mb PDF View/ Open

This item appears in the following Collection(s)

Show full item record