Software: Backbone Guided WalkSAT for SAT and Max-SAT with Dynamic Noise Ratio

Moshe Looks, Ananda Rangan and Weixiong Zhang
Department of Computer Science and Department of Genetics
Washington University in St. Louis, St. Louis, MO 63130, USA
email:  moshelooks@yahho.com, zhang@cse.wustl.edu

Here is the package of programs we developed for the backbone guided WalkSAT algorithm with dynamic noise ratio for SAT and Max-SAT.  Our software was built on top of the WalkSAT local search algorithm and software (downloaded from Henry Kautz's homepage).  The original idea of the dynamic noise ratio method was due to Holger Hoos.  We implemented (after some struggling effort) and tested it on 3-SAT and Max-3-SAT.  To learn more about the backbone guided local search method with dynamic noise ratio, take a look at a paper presented at IJCAI-03.

The package can be downloaded as a gzipped tar file or a WinZip file. Use "tar -zxvf filename" to unzip the package.  See the README file for details on installation and usage.  We used a Linux box for the development and test.

Note:  The README file should be sufficient for a quick installation and use of the software.  We cannot guarantee any support.