Publication: On universal restart strategies for backtracking search.

All || By Area || By Year

Title	On universal restart strategies for backtracking search.
Authors/Editors*	H. Wu, P. van Beek
Where published*	Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming, Providence, RI
How published*	Proceedings
Year*	2007
Volume
Number
Pages	681-695
Publisher
Keywords
Link
Abstract	Constraint satisfaction and propositional satisfiability problems are often solved using backtracking search. Previous studies have shown that a technique called randomization and restarts can dramatically improve the performance of a backtracking algorithm on some instances. We consider the commonly occurring scenario where one is to solve an ensemble of instances using a backtracking algorithm and wish to learn a good restart strategy for the ensemble. In contrast to much previous work, our focus is on universal strategies. We contribute to the theoretical understanding of universal strategies and demonstrate both analytically and empirically the pitfalls of non-universal strategies. We also propose a simple approach for learning good universal restart strategies and demonstrate the effectiveness and robustness of our approach through an extensive empirical evaluation on a real-world testbed.