A multistage optimization method based on WALKSAT and clustering for the hard MAX-SAT problems

It is widely recognized that WALKSAT is the one of the most effective local search algorithm for the satisfiability (SAT) and maximum satisfiability (MAX-SAT) problems. Inspired by the idea of population learning the large-scale structure of the landscape, this paper presents a multistage optimization method called MS-WALKSAT, which is based on WALKSAT and clustering. The experimental results on a variety of large and hard MAX-SAT problem instances have shown the MS-WALKSAT provides better performance than most of the reported algorithms.