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
2 ENPC - École des Ponts ParisTech
3 LIGM - Laboratoire d'Informatique Gaspard-Monge
4 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
5 PUCV - Pontificia Universidad Católica de Valparaíso
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.
Keywords : Global Optimization Interval Branch and Bound Node Selection
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 : jeudi 26 juillet 2018 - 12:16: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

Collections

ENPC | IMAGINE | LIGM_A3SI | COCONUT | LIGM | LIRMM | UPEC-UPEM | MIPS | UNIV-MONTPELLIER | PARISTECH | ESIEE-PARIS

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

564

Téléchargements de fichiers

475

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD