Complete Local Search for Propositional Satisfiability

Hai Fang, Wheeler RumlAAAI 2004

Introduction

In the field of automated reasoning, the Propositional Satisfiability (SAT) problem has historically been approached through two distinct methodologies. On one side are systematic tree-based searches, such as the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, which are "complete"—they are mathematically guaranteed to eventually find a solution or provide a formal proof of unsatisfiability. On the other side are stochastic local search (SLS) algorithms, like WalkSAT, which are often significantly faster at finding solutions for certain hard satisfiable instances but are "incomplete." If an SLS algorithm fails to find a solution, it remains unknown whether the problem is truly unsatisfiable or if the search simply failed to locate the satisfying assignment.

This paper introduces Complete Local Search (CLS), a framework that successfully bridges this gap. CLS is the first local search algorithm for SAT that is mathematically guaranteed to be complete, allowing it to navigate out of local minima and eventually prove unsatisfiability.

The CLS Framework

The core innovation of CLS lies in its ability to dynamically modify the search landscape to escape local minima. The algorithm follows a structured four-step process:

  1. Hill-Climbing: The search begins with a random assignment and flips variables only if the move strictly improves a specific "objective function."
  2. Escape via Learning: When the search reaches a local minimum where no single flip offers improvement, CLS performs Neighborhood Resolution. It derives a new "implied clause"—a logical consequence of the existing formula—that is specifically violated by the current state.
  3. Landscape Smoothing: This learned clause is added to the formula. Since the objective function is tied to the clauses, adding this constraint effectively "fills in" the local minimum, reshaping the landscape so the current state is no longer a trap.
  4. Lexicographical Objective Function: To ensure completeness, CLS employs a novel objective function that ranks assignments based on a tuple representing the number of violated clauses of each possible length. This mathematical structure ensures the search never loops infinitely and systematically moves toward a state of "implication closure."

Experimental Evaluation

The authors evaluated CLS using the comprehensive 2003 SAT Competition benchmarks, which include 996 instances across three distinct categories: Random (stochastically generated), Handmade (difficult puzzles), and Industrial (real-world encodings from hardware verification and planning).

Performance comparison of CLS against other state-of-the-art SAT solvers across different benchmark categories.

As shown in the table above, CLS demonstrated significant competitive strength. It outperformed every other local search solver in the competition (such as RSAPS) in terms of the total number of problem "series" solved. Specifically, CLS solved 39 series and 209 instances, compared to 30 series and 212 instances for RSAPS. Notably, the "CLS (sat only)" row highlights that while its performance on satisfiable instances is strong, its true power lies in its ability to handle the full benchmark set, including unsatisfiable instances that traditional local search solvers cannot address.

Key Insights and Results

  • Resolution as a Geometric Tool: The paper re-envisions logical resolution not just as a means of fact-finding, but as a geometric tool to reshape search spaces. Adding a learned clause acts like pouring cement into a hole in the landscape.
  • Industrial Strength: Because CLS can prove unsatisfiability, it vastly outperformed traditional local search on industrial benchmarks, which frequently contain unsatisfiable sub-problems.
  • Bridging the Gap: The results confirm that a completeness guarantee does not necessitate a massive performance penalty. CLS maintains the efficiency of local search on random instances while possessing the formal power of a tree-based solver.

Conclusion and Future Work

While CLS represents a major milestone, it faces challenges regarding space complexity, as the database of learned clauses can grow significantly. Future research may focus on "clause forgetting" techniques—common in modern DPLL solvers—to maintain efficiency over long search durations. Nevertheless, CLS proves that the "holy grail" of SAT research—a complete local search algorithm—is both theoretically possible and practically viable.

Summary updated

BibTeX
@inproceedings{fang2004complete,
  author = {Hai Fang and Wheeler Ruml},
  title = {{Complete Local Search for Propositional Satisfiability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2004},
}
Figure