Generalized disjunctive programming: A framework for formulation and alternative algorithms for MINLP optimization
Presenter
November 21, 2008
Keywords:
- Nonconvex programming
MSC:
- 90C26
Abstract
Generalized disjunctive programming (GDP) is an extension of the disjunctive programming paradigm developed by Balas. The GDP formulation involves Boolean and continuous variables that are specified in algebraic constraints, disjunctions and logic propositions, which is an alternative representation to the traditional algebraic mixed integer programming (MIP) formulation. Our research on GDP problems has been motivated by its potential for improved modeling of MINLP optimization, and for the development of customized algorithms that exploit the underlying logical structure of the problem in both the linear and nonlinear cases. We first provide an overview of this work for the case of convex functions emphasizing the quality of continuous relaxations of alternative reformulations that include the big-M, the hull relaxation and the sequential intersection of disjunctions. We then review disjunctive branch and bound as well as logic-based decomposition methods that circumvent some of the limitations in traditional MINLP optimization. Finally, for the case when the GDP problem involves nonconvex functions, we propose a scheme for tightening the lower bounds for obtaining the global optimum using a combined disjunctive and spatial branch and bound search. We illustrate the application of the theoretical concepts and algorithms on a variety of engineering and OR problems.