Generalized Disjunctive Programming, originally developed by Raman and Grossmann (1994) as a framework that facilitates the modeling of discrete-continuous optimization problems, has led to the development of customized algorithms that are aimed at exploiting the underlying logical structure of the problem, in both the linear [Raman & Grossmann, 1994] and nonlinear cases [Turkay & Grossmann, 1996; Lee & Grossmann, 2000]. One of the main key issues that GDP problems face is the appropriate selection of the MILP/MINLP reformulation from where the problem can be finally solved. (e.g. Convex Hull reformulation Lee & Grossmann, 2000). Sawaya & Grossmann (2007) have recently made a novel contribution in GDP by establishing new connections with the foundation of this technique, namely with Disjunctive Programming theory [Balas 1974]. As a result, a family of tighter reformulations have been identified, which are obtained by performing a sequence of basic steps on the original disjunctive set (i.e. each step is characterized by generating a new set of disjunctions by intersecting the former), bringing it to a form closer to the DNF [Balas, 1985] and hence tightening its relaxation.
It is in the aim of this work to build on the work by Sawaya & Grossmann (2006) exploiting the newly discovered hierarchy of relaxations in order to solve non-convex GDP problems with bilinearities. The basic approach consists in first relaxing the bilinear terms using convex envelopes [McCormick, 1976] and then introducing them as part as the disjunctive set prior to the application of the basic steps. This reformulation leads to stronger lower bounds, even when a small number of basic steps are used. This in turn leads to an improvement in the performance of the disjunctive spatial branch and bound method suggested by Lee & Grossmann (2001). A number of basic theoretical properties are established and proved for the proposed method. In addition, a set of examples and case studies are presented to illustrate the computational efficiency of the method and to compare it with previous methods.
Raman, R., & Grossmann, I. E. (1994). Modeling and computational techniques for logic based integer programming. Computers and Chemical Engineering, 18(7), 563-578
Sawaya N. & Grossmann I. E. (2007) Reformulation, Relaxation and Cutting Planes for Linear Generalized Disjunctive Programming, manuscript in preparation.
Turkay & Grossmann I.E. (1996) Logic Based MINLP algorithms for the optimal synthesis of process networks. Computers and Chemical Engineering, 20(8), 959-978.
Sangbum L. & Grossmann I. E. New algorithms for nonlinear generalized disjunctive programming. Computers and Chemical Engineering 24 (2000) 2125-2141.
Sangbum L. & Grossmann I. E. Global Optimization Algorithm for nonconvex generalized disjunctive programming and applications to process systems. Computers and Chemical Engineering 24 (2001) 1675-1697.
McCormick, G. P. (1976) Computability of global solutions to factorable nonconvex programs. Part I. Convex underestimating problems. Mathematical Programming, 10, 146-175.