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

Translated title of the contribution: Node selection in interval Branch and Bound algorithms

Bertrand Neveu, Gilles Trombettoni, IGNACIO DANIEL ARAYA ZAMORANO

Research output: Contribution to conferencePaperpeer-review

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.

Translated title of the contributionNode selection in interval Branch and Bound algorithms
Original languageFrench
Pages236-245
Number of pages10
StatePublished - 1 Jan 2015
Event11th French Speaking Symposium on Constraint Programming, JFPC 2015 - Bordeaux, France
Duration: 22 Jun 201524 Jun 2015

Conference

Conference
Country/TerritoryFrance
CityBordeaux
Period22/06/1524/06/15

Fingerprint

Dive into the research topics of 'Node selection in interval Branch and Bound algorithms'. Together they form a unique fingerprint.

Cite this