Flexible Computation and Representation: The Next 10 Years

nTo date: success with simple fixed policy:

Restart search if run-time is greater than x

nOrders of magnitude speedup

Time to Solution

Time expended before restart

100-1000x

Decisom Model for Dynamic Restart Policies

Gomes, et al. 1997

Eric Horvitz, April 5, 2003


	This could be very successful in practice. Insights from simulated annealing should be very useful.

	The horizontal axis gives different restart rates. The vertical axis gives the time till solution (logarithmic). We see how one can achieve orders of magnitude speedups by choosing the right restart rate.