Feasibility Verification and Upper Bound Computation in Global Minimization Using Approximate Active Index Sets

Christian Füllner (), Peter Kirst (), Hendrik Otto () and Steffen Rebennack ()
Additional contact information
Christian Füllner: Institute for Operations Research, Stochastic Optimization, Karlsruhe Institute of Technology, 76199 Karlsruhe, Germany
Peter Kirst: Operations Research and Logistics, Wageningen University & Research, 6708 PB Wageningen, Netherlands
Hendrik Otto: Institute for Operations Research, Stochastic Optimization, Karlsruhe Institute of Technology, 76199 Karlsruhe, Germany
Steffen Rebennack: Institute for Operations Research, Stochastic Optimization, Karlsruhe Institute of Technology, 76199 Karlsruhe, Germany

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1737-1756

Abstract: We propose a new upper bounding procedure for global minimization problems with continuous variables and possibly nonconvex inequality and equality constraints. Upper bounds are crucial for standard termination criteria of spatial branch-and-bound (SBB) algorithms to ensure that they can enclose globally minimal values sufficiently well. However, whereas for most lower bounding procedures from the literature, convergence on smaller boxes is established, this does not hold for several methods to compute upper bounds even though they often perform well in practice. In contrast, our emphasis is on the convergence. We present a new approach to verify the existence of feasible points on boxes, on which upper bounds can then be determined. To this end, we resort to existing convergent feasibility verification approaches for purely equality and box constrained problems. By considering carefully designed modifications of subproblems based on the approximation of active index sets, we enhance such methods to problems with additional inequality constraints. We prove that our new upper bounding procedure finds sufficiently good upper bounds so that termination of SBB algorithms is guaranteed after a finite number of iterations. Our theoretical findings are illustrated by computational results on a large number of standard test problems. These results show that compared with interval Newton methods from the literature, our proposed method is more successful in feasibility verification for both, a full SBB implementation (42 instead of 26 test problems) and exhaustive sequences of boxes around known feasible points (120 instead of 29 test problems).

Keywords: branch-and-bound; deterministic upper bounds; feasibility verification; active index sets; global optimization; convergence (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0162 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1737-1756

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().