TL;DR
This paper introduces three novel strategies—clause weighting, averaging in previous solutions, and random walks—that significantly enhance the performance of GSAT, a randomized local search algorithm for propositional satisfiability (SAT) problems. These extensions allow GSAT to tackle larger and more complex structured problems, previously intractable for the basic algorithm, by effectively uncovering hidden problem structure.
What Problem Does This Paper Address?
Propositional satisfiability (SAT) is a fundamental problem in computer science with applications in areas like artificial intelligence planning and hardware verification. While algorithms like GSAT (a randomized local search approach) can efficiently solve large, randomly generated SAT instances, they struggle with problems exhibiting intricate, hidden structures. These structured problems, such as those arising from blocks-world planning or certain graph coloring instances, often lead GSAT into local optima from which it cannot escape. Traditional methods like the Davis-Putnam procedure (a backtracking search algorithm) can handle some structured problems better due to their explicit mechanisms for exploiting structure (e.g., unit propagation), but they often scale poorly. This paper aims to bridge this gap by developing domain-independent extensions to GSAT that enable it to effectively solve these challenging structured SAT instances.
Methods
The paper proposes three key strategies to augment the basic GSAT algorithm:
- Strategy 1: Clause Weights: This approach assigns weights to clauses, effectively treating a clause with weight L as if it appeared L times. The weights are dynamically adjusted: at the end of each "try" (a complete run of GSAT), the weights of unsatisfied clauses are incremented. This helps GSAT focus on problematic clauses and discover hidden asymmetries in the problem structure.
- Strategy 2: Averaging in Previous Near Solutions: Instead of starting each new "try" with a completely random assignment, this strategy uses the best assignment found in the previous try to inform the initial assignment of the next try. Specifically, it computes a "bitwise average" of the current initial assignment and the best assignment found so far. This helps the search converge more quickly by leveraging information from successful past attempts.
- Strategy 3: Random Walk: This strategy introduces a probabilistic element to the search. With a certain probability (p), GSAT randomly selects an unsatisfied clause and flips the assignment of one of its variables. With the remaining probability (1-p), it follows the standard GSAT greedy approach of flipping the variable that yields the largest improvement. This "random walk" mechanism helps GSAT escape local minima by occasionally making moves that might not immediately improve the solution but can lead it to unexplored regions of the search space.
Datasets
The paper evaluates the proposed strategies on several types of benchmark problems:
- Hard Randomly Generated 3CNF Formulas: Used to demonstrate GSAT's initial advantage over DP and to show how extensions further improve performance.
- N-Queens Problems: A classic constraint satisfaction problem.
- Graph Coloring Problems: Specifically, challenging instances with asymmetries, including those from Ginsberg and Jönsson, and the benchmark problems used by Johnson et al. (1991).
- Boolean Induction Problems: Problems derived from inferring logical circuits from input-output behavior.
- Blocks-World Planning Problems: Including the "towers of Hanoi" problem, known for its highly structured nature and difficulty for basic GSAT.
The authors do not introduce new benchmark datasets but rather use existing, well-established problem classes known to be challenging for SAT solvers.
Key Insights and Ideas
- Structure is Key: The paper highlights that while GSAT excels on random problems, its limitations lie in its inability to inherently exploit problem structure. The proposed extensions are designed to "uncover" this hidden structure.
- Clause Weighting for Asymmetries: Assigning weights to clauses is a powerful way to handle problems with strong asymmetries, where certain constraints are implicitly more important than others. This strategy effectively "fills in" local minima caused by these imbalances.
- Leveraging Past Success: The averaging strategy demonstrates that information from previous search attempts can be effectively reused to guide the search, leading to faster convergence and the ability to solve problems that were previously intractable.
- Random Walk as a Local Minima Escape: The random walk mechanism provides a principled way to escape local optima, offering an alternative to the "noise" used in simulated annealing, by directly targeting unsatisfied clauses.
- Domain-Independence: A crucial aspect is that these strategies are "domain-independent," meaning they can be applied to various problem types without requiring specific knowledge of the problem domain (e.g., planning or graph coloring).
Key Results
- Clause Weighting: For asymmetrical graph coloring problems, this strategy reduced the number of unsatisfied clauses significantly, leading to a satisfying assignment in 80 out of 1000 tries, compared to none without weights. The time taken became comparable to efficient backtracking procedures.
- Averaging: This strategy enabled GSAT to solve two graph coloring instances that were previously unsolvable by GSAT and even by the Davis-Putnam procedure. It also made GSAT competitive with specialized graph coloring algorithms.
- Random Walk: When applied to Boolean induction problems, the random walk strategy substantially improved GSAT's performance, solving problems that were previously difficult.
- Combined Strategies: Combining all three strategies (weights, averaging, and random walk) allowed GSAT to solve planning problems (like towers of Hanoi) in a reasonable amount of time, achieving performance comparable to basic backtracking search, although highly optimized procedures were still faster.
Limitations and Future Work
- Theoretical Guarantees: The authors acknowledge that while the strategies are empirically effective, providing formal theoretical proofs of their effectiveness in practice is extremely difficult, similar to the challenges in theoretically explaining simulated annealing.
- Outperforming Specialized Solvers: For certain highly structured problems, domain-specific heuristics and backtracking search algorithms can still outperform GSAT, even with these extensions.
- Future Research: The authors plan to develop a more precise formal understanding of the benefits and applicability of these techniques. They also aim to explore alternative representations for planning problems that are more amenable to local search, making assignments that violate few constraints closer to satisfying assignments. The ultimate goal is to develop representations that are less fragile than traditional logical representations.
Summary updated