Optimization Online


Decomposing Optimization-Based Bounds Tightening Problems Via Graph Partitioning

Michael Bynum(mlbynum***at***sandia.gov)
Anya Castillo(anya.castillo***at***gmail.com)
Bernard Knueven(Bernard.knueven***at***nrel.gov)
Carl Laird(cdlaird***at***sandia.gov)
John Siirola(jdsiiro***at***sandia.gov)
Jean-Paul Watson(jeanpaulwatson***at***llnl.gov)

Abstract: 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.

Keywords: Global Optimization; Decomposition; Domain Reduction; Bounds Tightening

Category 1: Global Optimization


Download: [PDF]

Entry Submitted: 02/11/2021
Entry Accepted: 02/11/2021
Entry Last Modified: 02/11/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society