Branch and bound algorithm selection by performance prediction

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 ran-dom paths in the search tree. We present a simple adaptation of this estimator in the field of combinato-rial optimization problems, more precisely for an ex-tension of the maximal constraint satisfaction frame-work. Experiments both on random and strongly struc-tured 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