Papers › An Adaptive, Multivariate Partitioning Algorithm for Global Optimization of Nonconvex Programs
An Adaptive, Multivariate Partitioning Algorithm for Global Optimization of Nonconvex Programs
Harsha Nagarajan, Mowen Lu, Site Wang, Russell Bent, Kaarthik Sundar
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections