Publication: On portfolios for backtracking search in the presence of deadlines.

All || By Area || By Year

Title	On portfolios for backtracking search in the presence of deadlines.
Authors/Editors*	H. Wu, P. van Beek
Where published*	Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, Patras, Greece,
How published*	Proceedings
Year*	2007
Volume
Number
Pages
Publisher
Keywords
Link
Abstract	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.