(101f) Tightening Methods Based on Nontrivial Upper Bounds of Bilinear Terms for Pooling and Blending Models

Global optimization of nonconvex problems containing bilinear terms has received considerable attention (Gounaris et al., 2009; Kolodziej et al., 2013). Here, we focus on the bilinear term xy with nonnegative continuous variables x and y that are upper bounded by x^U and y^U, respectively. We consider xy is also upper bounded by a positive parameter γ, which is said to be a nontrivial upper bound on xy if γ<x^Uy^U.Many models for Process Systems Engineering problems contain nontrivial upper bounds on bilinear terms. Consider, for example, the outlet flow from a storage tank. One can model such flow using a bilinear term, in which the inventory of storage tank is multiplied with the split fraction. Since inventory is upper bounded by the tank capacity and split fraction is upper bounded by one, the upper bound on the flow derived from inventory and split fraction is the tank capacity. However, the flow is also upper bounded by the pipeline capacity, which is typically smaller than the tank capacity. Thus, pipeline capacity can be a nontrivial upper bound on bilinear term for the outlet flow from a storage tank. We note that while nontrivial upper bounds on bilinear terms are common in a wide range of problems, research on such bounds is limited.

In this talk, we derive a family of linear constraints that are valid for bilinear terms with nontrivial upper bounds. We first study the hyperbola xy=γ with γ being a nontrivial upper bound on xy, and derive the close form formula for a family of lines that are tangents to the hyperbola. We then translate such lines into constraints that are valid for the hyperbola, and lift these constraints to make them valid for the bilinear term xy. We show that, in the presence of nontrivial upper bound, the lifted constraints tighten the convex relaxation of bilinear term obtained using the method proposed by McCormick (McCormick, 1976). We propose an efficient separation algorithm that returns strong valid constraints from the family. We implement our method in a branch and bound algorithm for the pooling problem to illustrate its effectiveness in terms of tightening the relaxation at individual nodes and reducing computational time. We further test our method on different models for multiperiod crude blending problem with distillation, where we use a swing-cut model for the distillation to account for additional operating flexibility. Results indicate our method can substantially reduce computational requirements.

Reference

Gounaris, C. E., Misener, R., & Floudas, C. A. (2009). Computational Comparison of Piecewise−Linear Relaxations for Pooling Problems. Industrial & Engineering Chemistry Research, 48(12), 5742–5766. https://doi.org/10.1021/ie8016048

Kolodziej, S. P., Castro, P. M., & Grossmann, I. E. (2013). Global optimization of bilinear programs with a multiparametric disaggregation technique. Journal of Global Optimization, 57(4), 1039–1063. https://doi.org/10.1007/s10898-012-0022-1

McCormick, G. P. (1976). Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems. Mathematical Programming, 10(1), 147–175. https://doi.org/10.1007/BF01580665