Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Relaxations for Convex Nonlinear Generalized Disjunctive Programs and their Application to Nonconvex Problems

This talk deals with the theory of reformulations and numerical solution of generalized disjunctive programming (GDP) problems, which are expressed in terms of Boolean and continuous variables, and involve algebraic constraints, disjunctions and propositional logic statements. We propose a framework to generate alternative MINLP formulations for convex nonlinear GDPs that lead to stronger relaxations by generalizing the seminal work by Egon Balas (1988) for linear disjunctive programs. We define for the case of convex nonlinear GDPs an operation equivalent to a basic step for linear disjunctive programs that takes a disjunctive set to another one with fewer conjuncts. We show that the strength of relaxations increases as the number of conjuncts decreases, leading to a hierarchy of relaxations. We prove that the tightest of these relaxations, allows in theory the solution of the convex GDP problem as an NLP problem. We present a guide for the generation of strong relaxations without incurring in an exponential increase of the size of the reformulated MINLP. We apply the proposed theory for generating strong relaxations to a dozen convex GDPs which are solved with a NLP-based branch and bound method. Compared to the reformulation based on the hull relaxation, the computational results show that with the proposed reformulations significant improvements can be obtained in the predicted lower bounds, which in turn translates into a smaller number of nodes for the branch and bound enumeration. We then briefly describe an algorithmic implementation to automatically convert a convex GDP into an MILP or MINLP using the concept of basic steps, and applying both big-M and hull relaxation formulations to the set of disjunctions.

We address the extension of the above ideas to the solution of nonconvex GDPs that involve bilinear, concave and linear fractional terms. In order to solve these nonconvex problems with a spatial branch and bound method, a convex GDP relaxation is obtained by using suitable under- and over-estimating functions of the nonconvex constraints. In order to predict tighter lower bounds to the global optimum we exploiting the hierarchy of relaxations for convex GDP problems. We illustrate the application of these ideas in the optimization of several process systems to demonstrate the computational savings that can be achieved with the tighter lower bounds. Finally, we discuss recent work aimed at automating convex GDP reformulations into MILP/MINLP models in which basic steps are applied selectively and a hybrid of big-M and hull reformulation constraints is used. In order to decrease the size of these reformulations, an algorithm is presented for the derivation of cutting planes derived from basic steps and that are used to strengthen big-M models. Computational experience is reported on a set of 19 instances of varying sizes and complexity.

Type of Seminar:
IfA Seminar
Prof. Ignacio Grossmann
Dept. Chemical Engineering, Carnegie Mellon University, Pittsburgh
Jun 20, 2014   16:15

ETZ E6, Gloriastrasse 35
Contact Person:

Manfred Morari
File Download:

Request a copy of this publication.
Biographical Sketch:
Ignacio E. Grossmann is the R. R. Dean University Professor of Chemical Engineering at Carnegie Mellon University. He was Department Head from 1994 to 2002, and is currently director of the "Center for Advanced Process Decision-making." He is a member of the National Academy of Engineering. Major AIChE awards include Computing in Chemical Engineering Award, William H. Walker Award, Warren Lewis Award, and Research Excellence in Sustainable Engineering. He has honorary doctorates from Abo Akademi, University of Maribor and Technical University of Dortmund. His research interests are in the areas of mixed-integer and logic-based optimization, stochastic programming, water and energy systems, and planning and scheduling and enterprise-wide optimization.