Bounds tightening or domain reduction is a critical refinement technique used in global optimization algorithms for nonlinear and mixed-integer nonlinear programming problems. Bounds tightening can strengthen convex relaxations and reduce the size of branch and bounds trees. An effective but computationally intensive bounds tightening technique is optimization-based bounds tightening (OBBT). In OBBT, each variable is typically minimized and maximized subject to a convex relaxation of the original problem in order to obtain tighter variable bounds. In this paper, we present two variants of a scalable bounds tightening algorithm that decomposes the majority of the bounds tightening problems into much smaller problems via graph partitioning. Numerical results on a set of optimal power flow test problems and problems from MINLPLib demonstrate that our proposed algorithms can be nearly as effective as traditional OBBT in terms of domain reduction. Furthermore, the algorithms are significantly more computationally efficient and scale much better with problem size. For large problems, our decomposition algorithm can be over an order of magnitude faster than traditional OBBT and nearly as effective.
Article
View Decomposing Optimization-Based Bounds Tightening Problems Via Graph Partitioning