(227f) Tightening Constraints for Bilinear Terms with Semi-Continuous Variable and Nontrivial Bounds

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 w=xy with nonnegative variables x∈[x^L,x^U] and y∈[y^L,y^U], where w is semi-continuous and upper and lower bounded by w^U and w^L when positive. w^U and w^L are said to be nontrivial upper and lower bounds if w^U is smaller than x^U⋅y^U and w^L is greater than x^L⋅y^L, respectively. Many models for problems arise in Process Systems Engineering contain semi-continuous variable and nontrivial 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. We note that while the lower bounds on inventory and split fraction are both zero, in practice the outlet flow may be semi-continuous and lower bounded by a positive parameter; for upper bounds, we note that 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.

The convex hull of for bilinear terms with nontrivial bounds that contain only continuous variables has been studied by Belotti et al. (Belotti et al., 2010, 2011). Specifically, they showed that it can be described with infinitely many linear inequalities, some of which belong to a family of inequalities called “lifted tangent inequalities”. More recently, Anstreicher et al. derived closed-form representations for such convex hull with second-order cone constraints (Anstreicher et al., 2020).

In this talk, we derive a family of valid linear constraints for bilinear term with semi-continuous variable and nontrivial bounds and show that, in the presence of nontrivial bounds, such constraints tighten the convex relaxation of the bilinear term obtained using the McCormick inequalities (McCormick, 1976). We note that when the product of bilinear term is positive, the constraints presented in this talk coincide with a subset of the “lifted tangent inequalities”. However, compared to previous work by Belotti et al., the constraints proposed here are given in a different (parameterized) form, which enables straightforward optimization-based generation for such constraints. We apply our methods to the pooling problem that (1) contains only continuous variables, and (2) contains binary and semi-continuous variables. Computational results demonstrate the effectiveness of the proposed methods in terms of reducing the optimality gap and computational time.

References

Anstreicher, K. M., Burer, S., & Park, K. (2020). Convex Hull Representations for Bounded Products of Variables. ArXiv. http://arxiv.org/abs/2004.07233

Belotti, P., Miller, A. J., & Namazifar, M. (2010). Valid inequalities and convex hulls for multilinear functions. Electronic Notes in Discrete Mathematics, 36(C), 805–812. https://doi.org/10.1016/j.endm.2010.05.102

Belotti, P., Miller, A. J., & Namazifar, M. (2011). Linear inequalities for bounded products of variables. SIAG/OPT Views-and-News, 22(1), 1–8.

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