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]
2 ENPC - École des Ponts ParisTech
3 LIGM - Laboratoire d'Informatique Gaspard-Monge
4 COCONUT - Agents, Apprentissage, Contraintes
5 PUCV - Pontificia Universidad Católica de Valparaíso

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.

Mots clés: Global Optimization; Interval Branch and Bound; Node Selection

Domaines: Informatique [cs]; Recherche opérationnelle [cs.RO]; Informatique [cs]

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. ⟨hal-01077483⟩