Node selection strategies in interval Branch and Bound algorithmsReportar como inadecuado

Node selection strategies in interval Branch and Bound algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 ENPC - École des Ponts ParisTech 2 LIGM - Laboratoire d-Informatique Gaspard-Monge 3 IMAGINE Marne-la-Vallée 4 COCONUT - Agents, Apprentissage, Contraintes LIRMM - Laboratoire d-Informatique de Robotique et de Microélectronique de Montpellier 5 Pontificia Universidad Católica de Valparaíso

Abstract : We present in this article new strategies for selecting nodes in interval Branch and Bound algorithms for constrained global optimization. For a minimization problem the standard best-first strategy selects a node with the smallest lower bound of the objective function 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 node selection rule based on this criterion. We propose another strategy that also makes a trade-off 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.

Keywords : branch and bound global optimization

Autor: Bertrand Neveu - Gilles Trombettoni - Ignacio Araya -



Documentos relacionados