Node selection strategies in interval Branch and Bound algorithms - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Journal of Global Optimization Année : 2016

Node selection strategies in interval Branch and Bound algorithms

(1, 2, 3) , (4) , (5)
1
2
3
4
5

Résumé

We present in this article new strategies for selecting nodes in interval Branch and Bound algorithms for constrained global optimization. For a minimization problem the standard best-first strategy selects a node with the smallest lower bound of the objective function estimate. We first propose new node selection policies where an upper bound of each node/box is also taken into account. The good accuracy of this upper bound achieved by several contracting operators leads to a good performance of the node selection rule based on this criterion. We propose another strategy that also makes a trade-off between diversification and intensification by greedily diving into potential feasible regions at each node of the best-first search. These new strategies obtain better experimental results than classical best-first search on difficult constrained global optimization instances.
Fichier principal
Vignette du fichier
jogotas2.pdf (381.53 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01230893 , version 1 (19-11-2015)

Identifiants

Citer

Bertrand Neveu, Gilles Trombettoni, Ignacio Araya. Node selection strategies in interval Branch and Bound algorithms. Journal of Global Optimization, 2016, 64 (2), pp.289-304. ⟨10.1007/s10898-015-0375-3⟩. ⟨hal-01230893⟩
468 Consultations
817 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More