Donald J. Patterson

Auto-Walksat: A Self-Tuning Implementation of Walksat

Auto-Walksat: A Self-Tuning Implementation of Walksat Screenshot

Stochastic search algorithms have proven to be very fast at solving many satisfiability problems [2,3,8]. The nature of their search requires careful parameter tuning to maximize performance, but depending on the problem and the details of the stochastic algorithm, the correct tuning may be difficult to ascertain [9]. In this paper we introduce Auto-Walksat, a general algorithm which automatically tunes any variant of the Walksat family of stochastic satisfiability solvers. We demonstrate Auto-Walksat’s success in tuning Walksat-SKC to the DIMACS benchmark problems with negligible additional overhead.(local copy)

Published in theĀ proceedings of SAT2001: Workshop on Theory and Application of Satisfiability Testing


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.