(529c) New Piecewise Relaxation with a Logarithmic Partitioning Scheme for Quadratically Constrained Problems

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. Its main advantage compared to spatial branch-and-bound algorithms [4,5] is that bilinear terms are tackled simultaneously instead of sequentially, following partitioning of one of the variables in every bilinear term. As a consequence, orders of magnitude reductions in computational time can be achieved when incorporated in 2-stage, MILP-NLP global optimization algorithms.

The piecewise relaxation from MDT can consider any number, N, of intervals in the partition but only becomes a logarithmic partitioning scheme when N is a power of the chosen basis for numeric representation [6]. Popular basis are 10 [3] and 2 [7]. In contrast, the logarithmic portioning scheme (LR) of Misener et al. [8] can handle any value of N. Recent research [6] has shown that LR and the piecewise McCormick envelopes from Grossmann and co-workers [9-10] are conceptually similar in the sense they can be derived from the convex hull relaxation [11] of a Generalized Disjunctive Program (GDP) [12] featuring the McCormick envelopes [13] inside the disjunction. The major difference is that is that LR needs just ⌈log₂N⌉ binary variables per partitioned variable instead of N, leading to a superior computational performance with increasing N. In contrast, MDT is derived from a different GDP [6].

Aiming at closing the gap between MDT and LR, we now generalize the MDT relaxation to benefit from a logarithmic partitioning scheme for a wider range of values for N. The idea is to select the optimal interval in the partition by using a mixed-radix numeral system, following the prime factorization of N.

The mixed-radix MDT is compared to its predecessor, the single base MDT (linear partitioning scheme) and to LR, by considering benchmark instances A0-A4, A6-A7, A9 and B4 of the well-known q- and tp-formulations of the pooling problem [14]. These are the ones that for N∈{6, 10, 12, 14, 15, 18}, can be tackled by at least one of the relaxation schemes in under one hour of computational time when using CPLEX 12.10 running in parallel deterministic mode (up to 16 threads) on an Intel i9-9900K desktop computer. Note that for a given N, all mixed-integer linear programming (MILP) relaxations compute the same upper bound for the profit maximization problem and so we can simply use the computational time metric to evaluate the performance.

The results over a set of 66 data points show that the new mixed-radix formulation has a 74.2% probability of being the fastest, compared to just 6.1% of the single base MDT. Thus, the generalization of the MDT relaxation had a major impact in computational performance. As for the LR relaxation, 10 of the 14 wins occurred for N=14 and 15, just before the big jump in computational time for N=18, caused by the increase in the number of binary variables per partitioned variable from 4 to 5. In conclusion, and despite requiring a larger number of binary variables, MDT was shown to be an overall better approach than LR when N is factorizable.

Acknowledgments: Financial support from 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] Castro, P.M., 2021. Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems. Optimization and Engineering. https://doi.org/10.1007/s11081-021-09603-5.

[7] 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.

[8] 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

[9] 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.

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

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

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

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

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