Reference : Guided Dive for the Spatial Branch-and-Bound
Scientific journals : Article
Engineering, computing & technology : Computer science
Guided Dive for the Spatial Branch-and-Bound
Gerard, Damien mailto [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore) >]
Koeppe, Matthias [University of California, Davis - UC Davis > Department of Mathematics > > >]
Louveaux, Quentin mailto [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation : Optimisation discrète >]
Journal of Global Optimization
Yes (verified by ORBi)
[en] spatial branch-and-bound ; local search ; globall optimization
[en] We study the spatial Brand-and-Bound algorithm for the global opti- mization of nonlinear problems. In particular we are interested in a method to find quickly good feasible solutions. Most spatial Branch-and-Bound-based solvers use a non-global solver at a few nodes to try to find better incumbents. We show that it is possible to improve the branching rules and the node priority by exploiting the solutions from the non-global solver. We also propose several smart adaptive strategies to choose when to run the non-global solver. We show that despite the time spent in solving more NLP problems in the nodes, the new strategies enable the algorithm to find the first good incumbents faster and to prove the global opti- mality faster. Numerous easy, medium size as well as hard NLP instances from the Coconut library are benchmarked. All experiments are run using the open source solver Couenne.

File(s) associated to this reference

Fulltext file(s):

Open access
GuidedDiveFinal.pdfAuthor postprint952.03 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.