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

Bertrand Neveu (1, 2, 3) , Gilles Trombettoni (4) , Ignacio Araya (5)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 imagine [Marne-la-Vallée]
3 ENPC - École des Ponts ParisTech
4 COCONUT - Agents, Apprentissage, Contraintes
5 PUCV - Pontificia Universidad Católica de Valparaíso

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.

Domaines: Recherche opérationnelle [math.OC]

Bertrand Neveu, Gilles Trombettoni, Ignacio Araya. Choix de noeud dans un algorithme de Branch and Bound sur intervalles. 11èmes Journées Francophones de Programmation par Contraintes (JFPC 2015), Jun 2015, Bordeaux, France. ⟨hal-01230883⟩