(101h) Multiparametric Disaggregation with a Generic Base for the Relaxation of a Bilinear Term

The multiparametric disaggregation technique (MDT) can be used to approximate [1] or relax a bilinear term [2-3] in the context of the global optimization of (mixed-integer) quadratically constrained problems, (MI)QCPs. It has the advantage of handling all bilinear terms simultaneously, by discretizing the domain of one of the variables appearing in every bilinear term, instead of treating them one by one, as in spatial branch-and-bound [4,5]. As a consequence, orders of magnitude reductions in computational time can be achieved when incorporated in 2-stage, MILP-NLP, global optimization algorithms.

An alternative to MDT is the piecewise McCormick (PCM) relaxation [6,7] that can use a number of binary variables that grows linearly [6-10] or logarithmically [10] with the number of partitions. Starting from a Generalized Disjunctive Program [11], we now derive a more compact piecewise McCormick formulation by using a convex hull reformulation [12]. The advantage is that it is more intuitive since it adds terms to the global McCormick envelopes [13]. More specifically, a nonnegative term is added to the two sets of underestimators and a nonpositive term is added to the two sets of overestimators. It becomes clearer that the piecewise McCormick relaxation is tighter, with the added terms becoming zero for a single partition, thus reducing to the standard McCormick relaxation. When selecting multiple partitions, it also becomes apparent that for the first and last partitions, one underestimator and one overestimator coincide with the global envelopes. This new formulation uses a linear number of binary variables.

The number of binary variables for MDT grows logarithmically with the number of partitions but until recently, only powers of ten could be handled. This limitation of MDT was important when dealing with large-scale problems, such as in refinery planning [14], for which MILP relaxations with just a few partitions per variable may be difficult to solve to optimality. Andrade et al. [15] recently enhanced the MDT by proposing the use of base 2 instead of 10. In this work, we extend their approach for a generic base in order to provide a detailed comparison between MDT and PCM when using just a few partitions. As a result, MDT can use either a linear or logarithmic number of binary variables, allowing for an apples to apples comparison with the two alternative piecewise McCormick relaxations.

The computational study involves a set of 16 benchmark pooling problems (instances A0-A9 and B0-B5 from Alfaki and Haugland [16]), which are solved using the p-, q- and tp- alternative formulations. We selected these instances for two reasons: (i) the large majority of them cannot be solved to optimality by the state-of-the-art commercial global optimization solvers; (ii) the relaxation from the q- and tp- formulations can be solved to optimality when using just two partitions (for all instances), with most handling 3 and 5 partitions and some 7.

The results show that the three relaxation approaches perform very similarly for two partitions. For 3 and 5 partitions, the piecewise McCormick relaxation with a linear number of partitions is the best, closely followed by the linear MDT (with either base 3 or 5), whereas the logarithmic approach by Misener et al. [10] is the worst. However, the latter becomes the best for 7 partitions and excels when the number of partitions increases while constrained to a power of two. In such conditions, it performs similarly to the base-2 logarithmic MDT and both can lead to orders of magnitude lower optimality gaps when compared to commercial solvers BARON and ANTIGONE.

Acknowledgments: Financial support from the National Natural Science Foundation of China, Grant No. 51874325 and Fundação para a Ciência e Tecnologia (FCT) through projects CEECIND/00730/2017 and UIDB/04561/2020.

References:

[1] Teles, J.P., Castro, P.M., Matos, H.A., 2013. Multi-parametric disaggregation technique for global optimization of polynomial programming problems. J. Glob. Optim. 55, 227–251.

[2] Kolodziej, S., Castro, P.M., Grossmann, I.E., 2013. Global optimization of bilinear programs with a multiparametric disaggregation technique. J. Glob. Optim. 57, 1039–1063.

[3] Castro, P.M., 2016. Normalized multiparametric disaggregation: an efficient relaxation for mixed- integer bilinear problems. J. Glob. Optim. 64, 765–784.

[4] Sahinidis, N. V., 2004. BARON: A general purpose global optimization software package. J. Glob. Optim. 8, 201–205.

[5] Misener, R., Floudas, C.A., 2014. ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations. J. Glob. Optim. 59, 503–526.

[6] Bergamini, M.L., Aguirre, P., Grossmann, I., 2005. Logic-based outer approximation for globally optimal synthesis of process networks. Comput. Chem. Eng. 29, 1914–1933.

[7] Karuppiah R, Grossmann I.E, 2006. Global optimization for the synthesis of integrated water systems in chemical processes. Comput Chem Eng 30, 650–73.

[8] Wicaksono, D.S., Karimi, I.A., 2008. Piecewise MILP under- and overestimators for global optimization of bilinear programs. AIChE Journal, 54, 991– 1008.

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

[10] Misener, R., Thompson, J,P, Floudas, C.A., 2011. APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Computers and Chemical Engineering 35,876–892

[11] Raman, R; Grossmann, I. E., 1994. Modeling and Computational techniques for Logic Based Integer Programming. Comput. Chem. Eng. 18, 563.

[12] Balas, E., 1985. Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems. SIAM J. Algebr. Discrete Math. 6 (3), 466.

[13] McCormick, G.P., 1976. Computability of global solutions to factorable nonconvex programs: Part I - Convex underestimating problems. Math. Program. 10, 147–175.

[14] Castillo Castillo, P., Castro, P.M., Mahalec, V., 2017. Global optimization algorithm for large-scale refinery planning models with bilinear terms. Ind. Eng. Chem. Res. 56, 530–548.

[15] Andrade, T., Oliveira, F., Hamacher, S., Eberhard, A., 2019. Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming. J. Glob. Optim. 73, 701–722.

[16] Alfaki, M., Haugland, D., 2013. Strong Formulations for the Pooling Problem. J. Glob. Optim. 56, 897-916.