(206h) A Global Optimization Algorithm for Qcps Relying on Piecewise Relaxations with Logarithmic Partitioning

In the optimization models encountered in Process Systems Engineering, bilinear terms are the most common source of non-convexities in the constraints. Such quadratically constrained problems (QCPs) can be solved to global optimality by commercial solvers like BARON, ANTIGONE and GUROBI, which mostly rely on spatial branch & bound (B&B) for convergence. A critical feature is the relaxation used in spatial B&B, with the preference still given to the one derived from the McCormick envelopes of the bilinear terms [1]. Nevertheless, a tighter but computationally more expensive relaxation can be derived after adding a set of binary variables, leading to a mixed-integer linear program (MILP) instead of a linear program (LP). The most efficient way to do it is by relying on logarithmic partitioning schemes [2] that, for the same number of binary variables, can return relaxation gaps that are orders of magnitude smaller [3] than their linear counterparts [4]. Note that the formulation can be as tight as desired, and so the challenge is to find the tradeoff leading to the lowest computational time. The approach suggested in this paper, is to adjust the settings controlling the quality and size of the relaxation formulation dynamically, after observing the behavior of the instance being solved.

The relaxation is primarily used to compute the dual bound on the objective function but can also be used to reduce the domain of the model variables [5], and to provide a good initialization for a local QCP solver like CONOPT to generate a high quality primal bound. The proposed global optimization algorithm is inspired by our previous work [6] and consists of the following four steps:

1. Computation of a quick dual bound through the LP relaxation. Such solution is then used as initialization for the solution of the QCP with a fast local solver, giving us the primal bound and the first optimality gap.
2.The user specifies a maximum time per execution of OBBT. If this value if greater than the estimated time required (number of problems multiplied by computational time of LP relaxation), LP-based OBBT is triggered. Better variable bounds are typically obtained, leading to an improved dual bound and a tighter optimality gap in the next step.
3. If the elapsed time is below the specified maximum, we proceed to the MILP relaxation, derived using the base-2 multiparametric disaggregation technique (MDT) with the lowest setting for all discretized variables [3]: 2 intervals per partition. The solution pool capability of the MILP solver is used to provide multiple initialization points for the local QCP solver to try to improve the primal bound.
4. We recompute the estimated time for OBBT and, if low enough, execute MILP-based OBBT [7]. Multiple iterations of steps 3 and 4, with increasing number of intervals per partition, will typically be executed.
5. Once the computational time of the MILP relaxation surpasses a certain threshold (defined by the user), we trigger spatial B&B until closing the optimality gap to the desired target or running out of time.

For performance evaluation we rely on a set of benchmark instances from the literature. They consist of 34 instances of the water-using network design problem, and 10 instances of the pooling problem for the q- and tp-formulations. The results for the water instances show that the new algorithm significantly outperforms BARON 22.7.23 and GUROBI 9.5.2 with respect to the optimality gap at termination, achieving a reduction of up to 4 orders of magnitude. For the pooling instances GUROBI was the best performer. Over all 54 instances, the new algorithm was the best at proving global optimality (22 instances vs. 3 and 9), BARON excelled at find the optimal solution (43), while GUROBI always generated tighter dual bounds than BARON at termination (1 h of wall-clock time limit).

Acknowledgments: Financial support from Fundação para a Ciência e Tecnologia (FCT) through project UIDB/04028/2020.

References:

[1] McCormick, G.P. (1976). Computability of global solutions to factorable nonconvex programs. Part I. Con- vex underestimating problems. Math Program 10,146.

[2] 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. Comput. Chem. Eng. 35, 876-892.

[3] Castro, P.M., Liao, Q., Liang, Y. (2022). Comparison of mixed‐integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems. Optimization and Engineering 23, 717-747.

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

[5] Puranik, Y., Sahinidis, N. V. (2017). Domain reduction techniques for global NLP and MINLP optimization. Constraints 22, 338–376.

[6] Castro, P.M. (2017). Spatial branch-and-bound algorithm for MIQCPs featuring multiparametric disaggregation. Optim Methods Softw 32(4), 719–737

[7] Castro, P.M., Grossmann, I.E. (2014). Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems, J. Global Optim. 59, 277–306.