Abstract
GSAT is a randomized local search procedure for solving propositional satisfiability problems. GSAT can solve hard, randomly generated problems that are an order of magnitude larger than those that can be handled by more traditional approaches, such as the Davis-Putnam procedure. This paper presents the results of numerous experiments we have performed with GSAT in order to improve our understanding of its capabilities and limitations. We first characterize the space traversed by GSAT, noting a steep descent followed by broad flat plateaus. We then compare GSAT with simulated annealing and report on extensions like clause weights and averaging near-solutions that dramatically improve performance on structured problems.
Introduction
Propositional satisfiability (SAT)—determining if there is a true/false assignment that satisfies a set of logical clauses—is the foundational NP-complete problem. In the early 1990s, systematic solvers like the Davis-Putnam (DP) procedure were the gold standard, but they hit a "complexity wall" at relatively small problem sizes (around 350 variables). Selman and Kautz tackle the challenge of scaling SAT solvers to handle thousands of variables by moving away from exhaustive search toward stochastic local search.
Methods: The GSAT Procedure
The core of the paper is GSAT, a greedy local search procedure that operates through a simple iterative process:
- Initialize: Start with a completely random truth assignment.
- Flip: Identify the variable which, if its value is reversed, results in the greatest increase in the total number of satisfied clauses.
- Repeat: Keep flipping until a solution is found or a maximum number of "flips" is reached. If it fails, restart with a new random assignment.
The authors also introduce two critical extensions to the basic GSAT:
- Clause Weights: To handle "structured" problems where a few clauses are consistently ignored by the greedy heuristic, they assign weights to clauses. If a clause remains unsatisfied at the end of a try, its weight increases, forcing the algorithm to prioritize it in the next round.
- Averaging Initial Assignments: Instead of starting every "try" from scratch, they initialize new tries using a bitwise average of the best assignments found in previous attempts, effectively "warming up" the search.
Key Insights: Navigating the Plateaus
Perhaps the paper's most famous insight is the visualization of the search space. GSAT doesn't spend most of its time descending toward a solution. Instead, it spends approximately 95% of its time "wandering" on broad, flat plateaus where no single flip immediately improves the score.
The authors argue that GSAT is essentially a highly efficient way to execute the "low-temperature tail" of a simulated annealing schedule. While annealing allows "upward moves" to escape local minima, GSAT’s "sideways moves" on plateaus achieve a similar goal faster.
Key Results and Performance
GSAT significantly outperforms systematic DP solvers on large instances. While DP struggled with 350 variables, GSAT (with random walk extensions) could solve hard 1,500-variable formulas in under an hour.
On highly asymmetrical graph coloring problems that basic GSAT could never solve, the Clause Weights extension proved transformative. As shown in the experimental data, the weighted version found a solution in 80 out of 1,000 tries, whereas the basic version never reached zero unsatisfied clauses.
This weighting acts as a dynamic way to "fill in" local minima. By increasing the cost of violating specific clauses, the algorithm effectively reshapes the search landscape during the run to push the solver out of traps.
Limitations and Conclusion
As a local search method, GSAT is "incomplete." If it doesn't find a solution, one cannot determine if the formula is truly unsatisfiable or if the solver simply failed to find the assignment. Furthermore, while empirical results are strong, a formal characterization of why GSAT works so well on certain classes of formulas remains elusive. Despite these limitations, the experimental data identifies techniques worthy of formal analysis, bridging the gap between asymptotic theory and practical performance.
Summary updated