Efficient Implementations of SAT Local Search.
Alex S. Fukunaga · 2004
Abstract. Although most of the focus in SAT local search has been on search behavior (deciding which variable to flip next), the overall efficiency of an algorithm depends greatly on the efficiency of executing each variable flip and variable selection. This paper surveys, evaluates, and extends techniques and data structures that have been used in efficient implementations of SAT local search solvers (including GSAT and Walksat variants). 1