Node Selection Heuristics Using the Upper Bound in Interval Branch and Bound

Bertrand Neveu 1, 2, 3 Gilles Trombettoni 4 Ignacio Araya 5
1 IMAGINE [Marne-la-Vallée]
LIGM - Laboratoire d'Informatique Gaspard-Monge, CSTB - Centre Scientifique et Technique du Bâtiment, ENPC - École des Ponts ParisTech
4 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We present in this article a new strategy for selecting the current node in an interval Branch and Bound algorithm for constrained global optimization. The standard best-first strategy selects the node with the lowest lower bound of the objective estimate. We propose in this article 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 operators leads to a good performance of the criterion. These new strategies obtain better experimental results than classical best-first search on difficult instances.
Type de document :
Communication dans un congrès
MAGO-GOW: Global Optimization Workshop, Sep 2014, Malaga, Spain. 2014, XII Global Optimization Workshop Mathematical Applied Global Optimization. MAGO 2014
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal-enpc.archives-ouvertes.fr/hal-01077483
Contributeur : Bertrand Neveu <>
Soumis le : vendredi 24 octobre 2014 - 18:04:53
Dernière modification le : mercredi 30 mai 2018 - 17:22:02
Document(s) archivé(s) le : dimanche 25 janvier 2015 - 10:55:41

Fichier

17-MAGO.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01077483, version 1

Citation

Bertrand Neveu, Gilles Trombettoni, Ignacio Araya. Node Selection Heuristics Using the Upper Bound in Interval Branch and Bound. MAGO-GOW: Global Optimization Workshop, Sep 2014, Malaga, Spain. 2014, XII Global Optimization Workshop Mathematical Applied Global Optimization. MAGO 2014. 〈hal-01077483〉

Partager

Métriques

Consultations de la notice

499

Téléchargements de fichiers

403