Random Walk with Continuously Smoothed Variable We

Authors: Steven Prestwich

Publish Date: 2005/6/19

Volume: , Issue: , Pages: 203-215

PDF Link

Abstract

Many current local search algorithms for SAT fall into one of two classes Random walk algorithms such as Walksat/SKC Novelty+ and HWSAT are very successful but can be trapped for long periods in deep local minima Clause weighting algorithms such as DLM GLS ESG and SAPS are good at escaping local minima but require expensive smoothing phases in which all weights are updated We show that Walksat performance can be greatly enhanced by weighting variables instead of clauses giving the best known results on some benchmarks The new algorithm uses an efficient weight smoothing technique with no smoothing phase

Keywords: