(183d) Strengthening Lower Bounds in the Global Optimization of Bilinear and Concave Generalized Disjunctive Programs

This paper is concerned with the global optimization of Bilinear and Concave Generalized Disjunctive Programs. Nonconvex GDP problems with bilinear constraints are of particular interest since these arise in many applications, for instance, in the design of pooling problems (Meyer & Floudas, 2006), in the synthesis of integrated water treatment networks (Karuppiah & Grossmann, 2006), or generally, in the synthesis of process networks with multicomponent flows (Quesada & Grossmann, 1995). In addition, nonconvex GDP problems with concave constraints frequently arise when nonlinear investment cost functions are considered (Turkay & Grossmann, 1996). The NP-hard nature of these problems often leads to a great computational effort when searching for the global optimal solution. In particular, the efficiency of methods to solve these problems relies heavily on their capability to construct strong relaxations that yield tight lower bounds for the global optimum. In order to improve the computational efficiency of these methods, it is the major objective of this paper to propose a novel algorithmic procedure for finding such relaxations by exploiting the logical structure of the problems.

We first present and discuss a general framework to obtain a hierarchy of linear relaxations for nonconvex Generalized Disjunctive Programs (GDP). This framework combines the linear relaxation strategies proposed in literature for nonconvex MINLPs (McCormick, 1976, Al-Khayyal & Falk ,1983, Tawarmalani & Sahinidis , 2002) with the results in the work of Sawaya & Grossmann (2008), intimately related to the work of Balas (1985), to obtain relaxations for the case of Linear GDPs. We further exploit the theory behind Disjunctive Programming to guide the generation of stronger relaxations more efficiently by considering the particular structure of the problems. We show through a set of numerical examples that involve various applications in process systems engineering how these new relaxations can in a number of cases yield significantly stronger lower bounds compared to the case when no basic steps are applied. Finally, we discuss strategies through which these relaxations can be efficiently used under a spatial branch and bound framework.

Balas, E. (1985) Disjunctive Programming and a hierarchy of relaxations for discrete optimization problems. SIAM Journal on Algebraic and Discrete Methods, 6, 466-486.

Karuppiah, R. , Grossmann, I. E. (2006) Global optimization for the synthesis of integrated water systems in chemical processes. Computers and Chemical Engineering 20, 650-673

McCormick, G. P. (1976) Computability of global solutions to factorable nonconvex programs. Part I. Convex underestimating problems. Mathematical Programming, 10, 146-175.

Meyer C. and C.A. Floudas (2006) Global Optimization of a Combinatorially Complex Generalized Pooling Problem, AIChE Journal, 52, 1027-1037.

Quesada, I. & Grossmann I. E. (1995b) Global optimization of bilinear process networks with multicomponent flows. Computers and Chemical Engineering, 19 (12), 1219-1242.

Sawaya & Grossmann (2008) Reformulations, Relaxations and Cutting Planes for Linear Generalized Disjunctive Programming. Submitted for publication (2008)

Tawarmalani, M., Sahinidis, N. (2002) Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. , Kluwer Academic Publishers

Turkay M. & Grossmann I.E. (1996) Disjunctive Programming Techniques for the Optimization of Process Systems with Discontinuous Investment Costs-Multiple Size Regions. Ind. Eng. Chem. Res. 1996, 35, 2611-2623