Lionel Lobjois, Michel Lemaître
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.