# An Adaptive, Multivariate Partitioning Algorithm for Global Optimization of Nonconvex Programs

arXiv: https://arxiv.org/abs/1707.02514 · HTML: https://mlsanity.com/paper/1707.02514/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2017.

## Built on by (most cited first, 2 of 2)

- [Simplifying deflation for non-convex optimization with applications in Bayesian inference and topology optimization](https://mlsanity.com/paper/2201.11926/) (2022)
- [Tightening Discretization-based MILP Models for the Pooling Problem using Upper Bounds on Bilinear Terms](https://mlsanity.com/paper/2207.03699/) (2022)

## Abstract (arXiv)

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.