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
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.
Go to Artificial intelligence
Back to page 67 of list