(78b) Exploiting Vector Space Properties to Strengthen the Relaxation of Bilinear Programs Arising in the Global Optimization of Process Networks

In this paper we present a methodology for finding tight convex relaxations for a special set of quadratic constraints given by bilinear and linear terms that frequently arise in the optimization of process networks.

Process networks are one of the most frequent systems that are addressed in the optimization of processes [1] such as in the design of pooling systems [6], in the synthesis of integrated water networks [7] or in the design of heat exchanger networks [8]. In general process networks are composed of a set of nodes connected by a set of streams. Each stream is associated with a flow and a set of properties. The flows and properties of the set of streams leaving a node are related to the flow and properties of the set of streams entering the node and the characteristics of the node itself. The most frequent subset of equations found in these networks is represented by a set of bilinear and linear constraints, which often correspond to typical mass or energy balances. Although very simple in its representation, this set of constraints defines a nonconvex region, and when embedded in the final formulation, leads to the need of specialized global optimization techniques. Most of the practical methodologies to solve these global optimization problems rely on some variation of a spatial branch and bound framework [2] whose performance, in turn, heavily depends on generating strong relaxations. Some examples of spatial branch and bound implementations to solve process network problems can be found in Gounaris et al. [9] and Karuppiah and Grossmann [7]. In order to find a relaxation for the nonconvex set of constraints, the most frequent technique is based on the work by McCormick [3] in which each bilinear term is replaced by its convex envelope [10]. Note that this approach is a particular case of the Reformulation-Linearization Technique (RLT) [11] in which cuts are constructed by multiplying constraints by appropriate variables and then linearizing the resulting bilinear terms. Efficient implementations of this approach for large scale problems were studied by Liberty and Pantelides [12]. Other techniques consider the convex envelope of the summation of the bilinear terms [4] or the semidefinite relaxation of the whole set of bilinear terms [5]. Even though these techniques have shown to be successful in generating valid relaxations for general bilinear problems, they do not take advantage of the particular structure of the constraints.

With this in mind, the main objective of this paper is to propose a methodology for finding tighter convex relaxations for these set of constraints. The basic idea lies on exploiting the interaction between the vector spaces where the different set of variables are defined to tighten the relaxation of traditional approaches. In order to do so we first describe the system in vectorial form exposing the interaction of the different vector spaces. Second, we define and characterize the elementary building blocks of the system given by "minimal sets". This allows us to understand this interaction and generate from its properties cuts that are proved to be non-redundant for the original relaxation. Finally, we show that tighter relaxations are obtained with the proposed cuts in several data reconciliation problems of process networks [13] by embedding the resulting relaxation together with the McCormick convex envelopes within a spatial branch and bound framework.

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

[2] Horst, R. and Tuy, H., Global Optimization deterministic approaches (3rd Ed), Berlin: Springer-Verlag, 1996.

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

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

[5] Anstraicher K. M., Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, Journal of Global Optimization, 43(2-3): 471-484, 2009.

[6] Meyer, C. and Floudas, C.A., Global optimization of a combinatorially complex generalized pooling problem, AICHE Journal, 52, 1027-1037, 2006.

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

[8] Yee, T.F. and Grossmann, I.E. (1990). Simultaneous optimization model for heat integration - II Heat exchanger network synthesis, Computers and Chemical Engineering, 14, 1165-1184, 1990.

[9] Gounaris C.E., Misener R., and Floudas C.A., Computational comparison of piecewise-linear relaxations for pooling problems, Industrial & Engineering Chemistry Research, 48, 5742-5766 (2009).

[10] Al-Khayyal, F.A. and Falk, J.E.,Jointly constrained biconvex programming., Mathematics of Operations Research, 8(2):273-286, 1983.

[11] Sherali, H. D. and Alameddine,A.,A new reformulation linearization technique for bi-linear programming problems, Journal of Global Optimization 2: 379-410 , 1992.

[12] Liberti L. and Pantelides,An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms., Journal of Global Optimization, 36(2):161189, 2006.

[13] Narasimhan, S., Data reconciliation gross error detection : an intelligent use of process data, Gulf Professional Publishing, 2001.