Node selection through upper bounding local search methods in branch & bound solvers for NCOPs

Victor Reyes () and Ignacio Araya ()
Additional contact information
Victor Reyes: Universidad Diego Portales
Ignacio Araya: Pontificia Universidad Católica de Valparaíso

Journal of Global Optimization, 2025, vol. 91, issue 2, No 6, 355-369

Abstract: Abstract Interval-based branch & bound solvers are commonly used for solving Nonlinear Continuous global Optimization Problems (NCOPs). In each iteration, the solver strategically chooses and processes a node within the search tree. The node is bisected and the two generated offspring nodes are processed by filtering methods. For each of these nodes, the solver also searches for new feasible solutions in order to update the best candidate solution. The cost of this solution is used for pruning non-optimal branches of the search tree. Thus, node selection and finding new solutions, stands as pivotal aspects in the functionality of these kind of solvers. The ability to find close-to-optimal solutions early in the search process may discard extensive non-optimal search space regions, thereby effectively reducing the overall size of the search tree. In this work, we propose three novel node selection algorithms that use the feasible solutions obtained through a cost-effective iterative method. Upon updating the best candidate solution, these algorithms strategically choose the node containing this solution for subsequent processing. The newly introduced strategies have been incorporated as node selection methods in a state-of-the-art branch & bound solver, showing promising results in a set of 57 benchmark instances.

Keywords: Branch & Bound; Node selection; Upper bounding (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-024-01403-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jglopt:v:91:y:2025:i:2:d:10.1007_s10898-024-01403-2

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-024-01403-2

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().