Henry Kautz, Eric Horvitz, Yongshao Ruan, Carla Gomes, Bart Selman
Access postscript or pdf file.
We describe theoretical results and empirical study of context-sensitive restart policies for randomized search procedures. The methods generalize previous results on optimal restart policies by exploiting dynamically updated beliefs about the probability distribution for run time. Rather than assuming complete knowledge or zero knowledge about the run-time distribution, we formulate restart policies that consider real-time observations about properties of instances and the solver's activity. We describe background work on the application of Bayesian methods to build predictive models for run time, introduce an optimal policy for dynamic restarts that considers predictions about run time, and perform a comparative study of traditional fixed versus dynamic restart policies.
Keywords: Randomized search algorithms, restart policies, satisfiability (SAT) problems, quasigroup completion problem, graph coloring, logistics planning, constraint satisfaction (CSP), heavy-tailed distributions, NP-Complete problems.
In: Proceedings of the Eighteenth National Conference on Artificial Intelligence, Edmonton, Alberta, July 2002. AAAI Press.
Author Email: kautz@cs.washington.edu,horvitz@microsoft.com, ruan@cs.washington.edu, gomes@cs.cornell.edu, selman@cs.cornell.edu