Eric Horvitz, Yongshao Ruan, Carla P. Gomes, Henry Kautz, Bart Selman, David Maxwell Chickering
Access pdf file.
We describe research and results centering on the construction and use of Bayesian models that can predict the run time of problem solvers. Our efforts are motivated by observations of high variance in the time required to solve instances for several challenging problems. The methods have application to the decision-theoretic control of hard search and reasoning algorithms. We illustrate the approach with a focus on the task of predicting run time for general and domain-specific solvers on a hard class of structured constraint satisfaction problems. We review the use of learned models to predict the ultimate length of a trial, based on observing the behavior of the search algorithm during an early phase of a problem session. Finally, we discuss how we can employ the models to inform dynamic run-time decisions.
Keywords: Randomized search algorithms, restart policies, satisfiability (SAT) problems, constraint satisfaction (CSP), heavy-tailed distributions, quasigroup completion problem, NP-Complete problems.
In: Proceedings of the Seventeenth Conference on Uncertainty and Artificial Intelligence, Seattle, WA, August 2001, pp. 235-244. Morgan Kaufmann Publishers: San Francisco.
Author Email: horvitz@microsoft.com, ruan@cs.washington.edu, gomes@cs.cornell.edu, kautz@cs.washington.edu, selman@cs.cornell.edu, dmax@microsoft.com