Wed, 20 Aug 2008 22:04:15 BST CiteULike: bsilverthorn Ruan http://www.citeulike.org/user/bsilverthorn/author/Ruan CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/bsilverthorn/article/2708066 <i>Principles and Practice of Constraint Programming - CP 2002 (2002), pp. 175-200.</i><br /><br />The time required for a backtracking search procedure to solve a problem can be minimized by employing randomized restart procedures. To date, researchers designing restart policies have relied on the simplifying assumption that runs are probabilistically independent from one another. We relax the assumption of independence among runs and address the challenge of identifying an optimal restart policy for the dependent case. We show how offline dynamic programming can be used to generate an ideal restart policy, and how the policy can be used in conjunction with real-time observations to control the timing of restarts. We present results of experiments on applying the methods to create ideal restart policies for several challenging search problems using two different solvers. Restart Policies with Dependence among Runs: A Dynamic Programming Approach Yongshao Ruan Eric Horvitz Henry Kautz doi:10.1007/3-540-46135-3_38 Principles and Practice of Constraint Programming - CP 2002 (2002), pp. 175-200. 2008-04-23T16:11:16-00:00 2002 Principles and Practice of Constraint Programming - CP 2002 175 200 dynamic_programming restart_strategies http://www.citeulike.org/user/bsilverthorn/article/2708032 <i>(2002), pp. 674-681.</i> Dynamic restart policies Henry Kautz Eric Horvitz Yongshao Ruan Carla Gomes Bart Selman (2002), pp. 674-681. 2008-04-23T16:01:16-00:00 2002 674 681 American Association for Artificial Intelligence restart_strategies satisfiability http://www.citeulike.org/user/bsilverthorn/article/2294168 <i>(2001), pp. 235-244.</i> A Bayesian Approach to Tackling Hard Computational Problems Eric Horvitz Yongshao Ruan Carla Gomes Henry Kautz Bart Selman David Chickering (2001), pp. 235-244. 2008-01-27T00:42:19-00:00 2001 235 244 Morgan Kaufmann Publishers Inc. algorithm_portfolios algorithm_selection bayesian