Mixed integer programming approaches for nonlinear and stochastic programming

Mixed integer programming

Vielma Centeno, Juan Pablo ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Mixed integer programming;   

Others  :  https://smartech.gatech.edu/bitstream/1853/29624/1/vielma_centeno_juan_pablo_200908_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

In this thesis we study how to solve somenonconvex 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 isthe 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 constraintsby Ben-Tal and Nemirovski.We test thealgorithm 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 tolower 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 ofexisting 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.