Strong Partitioning and a Machine Learning Approximation for Accelerating the Global Optimization of Nonconvex Quadratically Constrained Quadratic Programs

Abstract

We learn optimal instance-specific heuristics for the global minimization of nonconvex quadratically constrained quadratic programs (QCQPs). Specifically, we consider partitioning-based convex mixed-integer programming relaxations for nonconvex QCQPs and propose the novel problem of strong partitioning to optimally partition variable domains without sacrificing global optimality. Because solving this max-min strong partitioning problem exactly can be very challenging, we design a local optimization method that leverages generalized gradients of the value function of its inner-minimization problem. However, even solving the strong partitioning problem to local optimality can be time consuming. To address this, we propose a simple and practical machine learning (ML) approximation for homogeneous families of QCQPs. Motivated by practical applications, we conduct a detailed computational study using the open-source global solver Alpine to evaluate the effectiveness of our ML approximation in accelerating the repeated solution of homogeneous QCQPs with fixed structure. Our study considers randomly generated QCQP families, including instances of the pooling problem, that are benchmarked using state-of-the-art global optimization software. Numerical experiments demonstrate that our ML approximation of strong partitioning reduces Alpine’s solution time by a factor of 2–4.5 on average, with maximum reduction factors ranging from 10 to 200 across these QCQP families.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0424 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0424 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .