Randomized Restarts
Solution: randomize the systematic solver
Add noise to the heuristic branching (variable choice) function
Cutoff and restart search after a fixed number of backtracks
Provably Eliminates heavy tails
In practice: rapid restarts with low cutoff can dramatically improve performance
(Gomes and Selman 1997, 1998)