Learning to Accelerate Partitioning Algorithms for the Global Optimization of Nonconvex Quadratically-Constrained Quadratic Programs

We learn optimal instance-specific heuristics to accelerate partitioning algorithms for solving nonconvex quadratically-constrained quadratic programs (QCQPs) to global optimality. Specifically, we propose the novel problem of strong partitioning to optimally partition the domains of variables participating in nonconvex terms within a QCQP without sacrificing guarantees of global optimality. We then design a local optimization method for solving this challenging max-min strong partitioning problem. Because solving this max-min problem to local optimality may still be time consuming, we propose to use machine learning (ML) to learn this strategy on homogeneous families of QCQPs. We present a detailed computational study on randomly generated families of QCQPs, including instances of the pooling problem, using the open-source global solver Alpine. Our numerical experiments demonstrate that strong partitioning and its ML approximation significantly reduce Alpine's solution time by factors of 3.5 - 16.5 and 2 - 4.5 on average and by maximum factors of 15 - 700 and 10 - 200, respectively, over different QCQP families.

Article

Download

View Learning to Accelerate Partitioning Algorithms for the Global Optimization of Nonconvex Quadratically-Constrained Quadratic Programs