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 contribution||Node selection in interval Branch and Bound algorithms|
|Number of pages||10|
|State||Published - 1 Jan 2015|
|Event||11th French Speaking Symposium on Constraint Programming, JFPC 2015 - Bordeaux, France|
Duration: 22 Jun 2015 → 24 Jun 2015
|Period||22/06/15 → 24/06/15|