Dynamic Restart Policies

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Satisfiability

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.