Hardness-Aware Restart Policies - Ruan, Yongshao; Horvitz, Eric; Kautz, Henry (IJCAI Workshop on Stochastic Search Algorithms, 2003)
Recent work has demonstrated that it is possible to boost the efﬁciency of combinatorial search procedures via the use of principled restart policies. We present a coupling of machine learning and dynamic programming that extends prior efforts by endowing restart policies with knowledge of the hardness of the speciﬁc instance being solved. This ability allows a restart policy to take into consideration an updated probability distribution over hardness as a previously unseen instance is being solved. We discuss the methods, highlighting their importance for real-world applications of combinatorial search. Finally, we present the empirical results.