Paper Info
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 nonconvex, Mixed-Integer Nonlinear Programs (MINLPs) with polynomial functions to global optimality. In particular, we present an iterative algorithm that exploits piecewise, convex relaxation approaches via disjunctive formulations to solve MINLPs that is different than conventional spatial branch-and-bound approaches. The algorithm partitions the domains of variables in an adaptive and non-uniform manner at every iteration to focus on productive areas of the search space. Furthermore, domain reduction techniques based on sequential, optimization-based bound-tightening and piecewise relaxation techniques, as a part of a presolve step, are integrated into the main algorithm. Finally, we demonstrate the effectiveness of the algorithm on well-known benchmark problems (including Pooling and Blending instances) from MINLPLib and compare our algorithm with state-of-the-art global optimization solvers. With our novel approach, we solve several large-scale instances, some of which are not solvable by state-of-the-art solvers. We also succeed in reducing the best known optimality gap for a hard, generalized pooling problem instance.
Year
DOI
Venue
2017
10.1007/s10898-018-00734-1
Journal of Global Optimization
Keywords
Field
DocType
Global optimization, Adaptive partitioning, MILP-based methods, Mixed-integer nonlinear programs, McCormick, Piecewise relaxations, Sequential optimization-based bound-tightening
Convergence (routing),Mathematical optimization,Nonlinear system,Global optimization,Iterative method,Pooling,Algorithm,Regular polygon,Solver,Piecewise,Mathematics
Journal
Volume
Issue
ISSN
74
4
0925-5001
Citations 
PageRank 
References 
3
0.41
39
Authors
5
Name
Order
Citations
PageRank
H. Nagarajan1489.37
Mowen Lu230.41
Site Wang340.78
Russell Bent47915.68
Kaarthik Sundar57511.68