Title: An Adaptive, Multivariate Partitioning Algorithm for Global Optimization of Nonconvex Programs,
Abstract: 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.