(275d) Global Optimization Of Bilinear Generalized Disjunctive Programs

This paper is concerned with the global optimization of Generalized Disjunctive Programs that involve bilinearites in the constraints. These problems arise in many industrial applications, for instance, in the design of pooling problems, in the synthesis of integrated water treatment networks, or generally in the synthesis of process networks with multicomponent flows. In order to improve the computational efficiency of disjunctive spatial branch and bound methods for solving these problems, this paper has as a major objective to make use of recent theoretical developments to predict new lower bounds. These are significantly tighter than the traditional lower bounds obtained from previous approaches that make direct use of the McCormick convex envelopes.

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.