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: firstname.lastname@example.org, email@example.com
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
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