Restart Policies with Dependence among Runs: A Dynamic Programming Approach

@incollection{citeulike:2708066, abstract = {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.}, author = {Ruan, Yongshao and Horvitz, Eric and Kautz, Henry }, citeulike-article-id = {2708066}, doi = {10.1007/3-540-46135-3\_38}, journal = {Principles and Practice of Constraint Programming - CP 2002}, keywords = {dynamic\_programming, restart\_strategies}, pages = {175--200}, posted-at = {2008-04-23 17:12:22}, priority = {0}, title = {Restart Policies with Dependence among Runs: A Dynamic Programming Approach}, url = {http://dx.doi.org/10.1007/3-540-46135-3\_38}, year = {2002} }

TY - CHAP ID - citeulike:2708066 L3 - citeulike-article-id:2708066 TI - Restart Policies with Dependence among Runs: A Dynamic Programming Approach JF - Principles and Practice of Constraint Programming - CP 2002 SP - 175 EP - 200 N2 - 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. KW - dynamic_programming KW - restart_strategies AU - Ruan, Yongshao AU - Horvitz, Eric AU - Kautz, Henry PY - 2002/// UR - http://dx.doi.org/10.1007/3-540-46135-3_38 ER -