On Portfolios for Backtracking Search in the Presence of Deadlines

@inproceedings{citeulike:2711111, 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 in- stances 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 backtrack- ing 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.}, author = {Wu, Huayue and van Beek, Peter }, booktitle = {19th IEEE International Conference on Tools with Artificial Intelligence - ICTAI 2007}, citeulike-article-id = {2711111}, doi = {10.1109/ICTAI.2007.38}, journal = {Tools with Artificial Intelligence, 2007. ICTAI 2007. 19th IEEE International Conference on}, keywords = {algorithm\_portfolios, complete\_search, deadlines}, pages = {231--238}, posted-at = {2008-04-24 01:55:14}, priority = {2}, title = {On Portfolios for Backtracking Search in the Presence of Deadlines}, url = {http://dx.doi.org/10.1109/ICTAI.2007.38}, volume = {1}, year = {2007} }

TY - CONF ID - citeulike:2711111 L3 - citeulike-article-id:2711111 TI - On Portfolios for Backtracking Search in the Presence of Deadlines T2 - 19th IEEE International Conference on Tools with Artificial Intelligence - ICTAI 2007 JF - Tools with Artificial Intelligence, 2007. ICTAI 2007. 19th IEEE International Conference on VL - 1 SP - 231 EP - 238 N2 - 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 in- stances 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 backtrack- ing 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. KW - algorithm_portfolios KW - complete_search KW - deadlines AU - Wu, Huayue AU - van Beek, Peter PY - 2007/// UR - http://dx.doi.org/10.1109/ICTAI.2007.38 ER -