Noise strategies for improving local search

It has recently been shown that local search is sur-prisingly good at nding satisfying assignments for certain computationally hard classes of CNF formu-las. The performance of basic local search methods can be further enhanced by introducing mechanisms for escaping from local minima in the search space. We will compare three such mechanisms: simulated annealing, random noise, and a strategy called \mixed random walk". We show that mixed random walk is the superior strategy. We also present results demon-strating the eectiveness of local search with walk for solving circuit synthesis and circuit diagnosis prob-lems. Finally, we demonstrate that mixed random walk improves upon the best known methods for solv-ing MAX-SAT problems