An Adaptive, Multivariate Partitioning Algorithm for Global Optimization of Nonconvex Programs
For researchers and practitioners solving nonconvex MINLPs, this algorithm offers a new approach that can handle previously intractable large-scale instances, though the improvement is incremental over existing spatial branch-and-bound methods.
The paper develops an adaptive multivariate partitioning algorithm for global optimization of nonconvex MINLPs with multi-linear terms, using piecewise polyhedral relaxations. It solves several large-scale instances intractable by state-of-the-art solvers and shrinks the best known optimality gap for a hard pooling problem instance.
In this work, we develop an adaptive, multivariate partitioning algorithm for solving mixed-integer nonlinear programs (MINLP) with multi-linear terms to global optimality. This iterative algorithm primarily exploits the advantages of piecewise polyhedral relaxation approaches via disjunctive formulations to solve MINLPs to global optimality in contrast to the conventional spatial branch-and-bound approaches. In order to maintain relatively small-scale mixed-integer linear programs at every iteration of the algorithm, we adaptively partition the variable domains appearing in the multi-linear terms. We also provide proofs on convergence guarantees of the proposed algorithm to a global solution. Further, we discuss a few algorithmic enhancements based on the sequential bound-tightening procedure as a presolve step, where we observe the importance of solving piecewise relaxations compared to basic convex relaxations to speed-up the convergence of the algorithm to global optimality. We demonstrate the effectiveness of our disjunctive formulations and the algorithm on well-known benchmark problems (including Pooling and Blending instances) from MINLPLib and compare with state-of-the-art global optimization solvers. With this novel approach, we solve several large-scale instances which are, in some cases, intractable by the global optimization solver. We also shrink the best known optimality gap for one of the hard, generalized pooling problem instance.