Branch and Bound Algorithm Selection by Performance Prediction

Abstract

We propose a method called Selection by Performance Prediction (SPP) which allows one, when faced with a particular problem instance, to select a Branch and Bound algorithm from among several promising ones. This method is based on Knuth's sampling method which estimates the efficiency of a backtrack program on a particular instance by iteratively generating random paths in the search tree. We present a simple adaptation of this estimator in the field of combinatorial optimization problems, more precisely for an extension of the maximal constraint satisfaction framework. Experiments both on random and strongly structured instances show that, in most cases, the proposed method is able to select, from a candidate list, the best algorithm for solving a given instance. Introduction The Branch and Bound search is a well-known algorithmic schema, widely used for solving combinatorial optimization problems. A lot of specific algorithms can be derived from this general schema. ...