(PDF) Huayue Wu and Peter van Beek. On portfolios for backtracking search in the presence of deadlines. Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, Patras, Greece, 231-238, October, 2007. A longer version appears in the International J. of AI Tools, (PDF), 17:835-855, 2008.
Constraint satisfaction and propositional satisfiability problems are often solved using backtracking search. Previous studies have shown that portfolios of backtracking algorithms---a selection of one or more algorithms plus a schedule for executing the algorithms---can dramatically improve performance on some instances. In this paper, we consider a setting that often arises in practice where the instances to be solved arise over time, the instances all belong to some class of problem instances, and a limit or deadline is placed on the computational resources that the backtracking algorithm can consume in solving any instance. For such a scenario, we present a simple scheme for learning a good portfolio of backtracking algorithms from a small sample of instances. We demonstrate the effectiveness of our approach through an extensive empirical evaluation on a real-world instruction scheduling testbed.