Choix de noeud dans un algorithme de Branch and Bound sur intervalles

Bertrand Neveu 1, 2, 3, * Gilles Trombettoni 4 Ignacio Araya 5
* Auteur correspondant
2 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
Résumé : Nous présentons dans cet article de nouvelles stra-tégies de choix de noeud dans un algorithme de Branch and Bound sur intervalles pour l'optimisation globale sous contraintes. La stratégie standard en meilleur d'abord choisit le noeud qui a la plus petite borne infé-rieure de l'estimation de l'objectif dans le domaine cor-respondant. Nous proposons d'abord de nouvelles stra-tégies qui prennent aussi en compte la borne supérieure de l'estimation de l'objectif. Une bonne précision sur cette borne supérieure , obtenue par l'application de plu-sieurs opérateurs de contraction, permet d'obtenir plus rapidement de bonnes solutions réalisables et donc de meilleures performances. Nous proposons egalement une autre stratégie qui réalise un compromis entre diversification et intensification en plongeant demanì ere gloutonne dans des régions potentiellement réalisables a chaque noeud de la recherche en meilleur d'abord. Ces nouvelles stratégies obtiennent de meilleurs résultats expérimen-taux que la recherche en meilleur d'abord sur des instances difficiles d'optimisation globale sous contraintes. Abstract We present in this article new strategies for selecting nodes in interval Branch and Bound algorithms for constrained global optimization. The standard best-first strategy selects a node with the lowest lower bound of the objective 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 criterion. We propose another strategy that also makes a tradeoff 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. * Ignacio Araya est financé en partie par le projet Fondecyt 11121366.
Type de document :
Communication dans un congrès
Onzièmes Journées Francophones de Programmation par Contraintes, Jun 2015, Bordeaux, France
Liste complète des métadonnées

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

https://hal-enpc.archives-ouvertes.fr/hal-01230883
Contributeur : Bertrand Neveu <>
Soumis le : jeudi 19 novembre 2015 - 11:02:40
Dernière modification le : jeudi 26 juillet 2018 - 12:16:02
Document(s) archivé(s) le : vendredi 28 avril 2017 - 21:13:04

Fichier

jfpctasfr1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01230883, version 1

Citation

Bertrand Neveu, Gilles Trombettoni, Ignacio Araya. Choix de noeud dans un algorithme de Branch and Bound sur intervalles. Onzièmes Journées Francophones de Programmation par Contraintes, Jun 2015, Bordeaux, France. 〈hal-01230883〉

Partager

Métriques

Consultations de la notice

248

Téléchargements de fichiers

211