Weighting for Godot: Learning Heuristics for GSAT

AAAI 1996

TL;DR

This paper introduces a novel weighting scheme for the GSAT local search algorithm, enhancing its ability to solve complex constraint satisfaction problems. By dynamically adjusting clause weights during search, the proposed Weighted GSAT (WGSAT) and its variants demonstrate significant improvements in both the number of problems solved and the efficiency of finding solutions compared to existing state-of-the-art methods.

What Problem Does This Paper Address?

Local search algorithms like GSAT are powerful tools for tackling computationally expensive problems, particularly those involving satisfiability (SAT). However, GSAT can get stuck in "plateaus" – situations where no single variable flip improves the number of satisfied clauses. This often leads to random exploration, which can be inefficient. While previous modifications have aimed to mitigate this, they often rely on random walks or complex heuristics. This paper addresses the challenge of improving GSAT's performance, especially on difficult problem instances, by developing a more informed and adaptive heuristic that leverages clause weights.

Methods

The core innovation is a "clause weights" scheme, building upon earlier work by Selman and Kautz. In this approach, each clause is assigned a weight, and the GSAT heuristic is modified to prioritize flips that maximize the total weight of satisfied clauses. Crucially, the authors introduce several novel variations:

  • Weight Update Frequency: Instead of updating weights only after a full "try" (a sequence of flips), they update them after each flip. This provides more immediate feedback to the heuristic.
  • Weight Function: They explore using a power function (∑ Wi^α * Sati(A)) for evaluating moves, giving higher-weighted clauses more influence.
  • Prior Weights: They investigate the impact of initializing clause weights to values other than 1, aiming to dampen initial "noisy" guidance.
  • Unsatisfied Variable Flipping (UGSAT): A variant that restricts flips to only variables within unsatisfied clauses, aiming for more focused exploration.

Datasets

The paper uses randomly generated 3-CNF (Conjunctive Normal Form) problems. These problems are specifically chosen to be near the "phase transition" – a region known to be particularly challenging for SAT solvers. The instances are generated such that they are guaranteed to have solutions, verified using a variant of the Davis-Putnam procedure. The authors also mention testing on "gerrymandered" graphs and problems like the Towers of Hanoi.

Key Insights and Ideas

  • Immediate Feedback is Key: Updating clause weights after every flip, rather than at the end of a try, significantly improves GSAT's ability to guide the search effectively. This allows the heuristic to adapt more rapidly to the current state of the search.
  • Weighting Schemes Matter: The choice of how to combine clause weights (e.g., simple sum vs. power function) and how to initialize them (prior weights) has a substantial impact on performance, especially for shorter search durations.
  • Focusing on Unsatisfied Clauses Can Be Efficient: The UGSAT variant, by restricting flips to unsatisfied clauses, shows promise for faster problem-solving, even if it might explore fewer states overall. This suggests a trade-off between exploration breadth and search efficiency.
  • Noise Reduction is Crucial for Early Search: Prior weights are shown to be important for initial guidance, particularly when the number of allowed flips (MaxFlips) is limited.

Key Results

  • Superior Single-Try Performance: WGSAT and its variants consistently outperform standard GSAT and HSAT (a known strong baseline) in terms of the proportion of problems solved within a single try, especially for higher values of MaxFlips.
  • Efficiency Gains: UGSAT, a variant of WGSAT, demonstrated a speedup of 5-6 times over WGSAT with a=1.0 in terms of total flips required to solve problems, indicating a more efficient search process.
  • Optimal Parameter Sensitivity: The effectiveness of prior weights is most pronounced for smaller MaxFlips values. For higher MaxFlips, the impact diminishes, suggesting that the search has more time to overcome initial noise.
  • Exponentiation Improves Performance: Using a power function (∑ Wi^α) for weight evaluation, particularly with α between 0.5 and 1.5, generally leads to better performance, especially as MaxFlips increases.

Limitations and Future Work

  • "Marginalized" Difficulty: The authors acknowledge that clause weights are not a true objective measure of difficulty but rather a reflection of the search's trajectory. This means the weights are specific to the path taken by the local search.
  • Extension to Other Structures: The paper suggests extending the weighting concept to sets of clauses, variables, and sets of variables, which could be particularly useful for problems with inherent structural properties (e.g., graph coloring).
  • Intelligent Prior Setting: The current approach of setting uniform prior weights is seen as a simplification. Future work could explore more intelligent methods for setting these initial weights.
  • Structured Problems: The authors express interest in testing WGSAT on more structured problem domains like chain CNFs, crossword puzzles, and quasigroup instances, as well as continuing investigations into problems like the Towers of Hanoi.

Summary updated

BibTeX
@inproceedings{1996weighting,
  title = {{Weighting for Godot: Learning Heuristics for GSAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure