PORTFOLIOS WITH DEADLINES FOR BACKTRACKING SEARCH
Huayue Wu, Peter van Beek · International Journal of Artificial Intelligence Tools · 2008
Backtracking search is often the method of choice for solving constraint satisfaction and propositional satisfiability problems. 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 can be consumed 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 using two testbeds: real-world instruction scheduling problems and the widely used quasigroup completion problems.