A Mixture-Model for the Behaviour of SLS Algorithms for SAT

AAAI 2002

TL;DR

This paper investigates why some "hard" SAT instances cause Stochastic Local Search (SLS) algorithms like WalkSAT to exhibit irregular, non-exponential run-time distributions (RTDs). The authors propose a novel mixture-model of exponential distributions to capture this behavior, linking it to "traps" in the search space and formalizing it with a simple Markov chain model. This work offers a deeper understanding of SLS performance and suggests avenues for improving these algorithms.

What Problem Does This Paper Address?

The propositional satisfiability problem (SAT) is a fundamental challenge in computer science. Stochastic Local Search (SLS) algorithms, such as WalkSAT and GSAT, have proven remarkably effective at solving large and difficult SAT instances. A common observation is that the run-time distributions (RTDs) of these algorithms on hard instances often follow a regular, exponential pattern. However, the underlying reasons for this regularity, and more importantly, the conditions under which it breaks down, remain largely unknown. This paper tackles this gap by exploring why certain hard SAT instances lead to irregular RTDs, deviating significantly from the expected exponential behavior, and seeks to explain this phenomenon.

Methods

The core of this research involves analyzing the run-time distributions (RTDs) of SLS algorithms.

  • Empirical Analysis of RTDs: The authors meticulously collect RTDs for WalkSAT and GWSAT on various SAT instances, particularly those from the "phase transition region" of Uniform Random-3-SAT. They use statistical tests (specifically, $\chi^2$ tests) to assess how well these empirical RTDs fit standard exponential distributions.
  • Mixture Models: When standard exponential distributions fail to capture the RTDs, the researchers propose using mixtures of exponential distributions. They demonstrate that a simple 2-component mixture model can effectively approximate these irregular RTDs.
  • Hypothesis Generation and Testing:
    • Multiple Solutions Hypothesis: Initially, they hypothesize that the presence of multiple solutions and their "basins of attraction" might cause mixture RTDs. They test this by modifying algorithms to start from fixed initial assignments and by analyzing single-solution instances.
  • Traps and Stagnation Hypothesis: The results from the multiple solutions hypothesis lead them to propose an alternative: "traps" in the search space. These are attractive regions that do not contain solutions, causing the search to stagnate.
  • Constructing Trap Instances: To test the trap hypothesis, they devise a method to create new SAT instances by "plugging" together easy single-solution instances. This creates a scenario where one component instance acts as a trap for the SLS algorithm.
  • Abstract Markov Chain Model: Based on the trap hypothesis, they develop a simplified Markov chain model. This model uses states to represent regions of the search space and transitions to represent the algorithm's movement. They introduce a "branched model with trap" to specifically represent the stagnation caused by traps.

Datasets

The primary datasets used in this study are instances from the Uniform Random-3-SAT distribution, specifically focusing on those in the "phase transition region."

  • SATLIB: The authors heavily rely on instances from the SATLIB repository, including:
  • uf100-430 (a set of critically constrained instances)
    • uf50-218
    • uf20-91
  • Newly Constructed Datasets:
    • Single-solution instances: Generated by filtering standard Uniform Random-3-SAT instances to find those with exactly one solution.
  • Plugged combination instances: Created by combining two single-solution instances using a specific construction (CP1[F, G] and CP2[F, G]) to introduce a trap.

Key Insights and Ideas

  • Irregular RTDs are Real and Explainable: The paper convincingly shows that irregular RTDs are not just noise but a genuine phenomenon for certain hard SAT instances, deviating from the typical exponential behavior.
  • Mixture Models as a Powerful Tool: The finding that simple mixtures of exponential distributions can accurately model these irregular RTDs is significant. It provides a quantitative way to characterize this complex behavior.
  • Traps, Not Just Multiple Solutions, Cause Stagnation: The experiments strongly suggest that "traps" – attractive but solution-less regions in the search space – are the primary cause of the observed search stagnation and irregular RTDs, rather than simply the presence of multiple solutions.
  • A Simple Markov Chain Captures Complex Behavior: The development of a basic Markov chain model (especially the branched version with a trap) that replicates the observed irregular RTDs is a major conceptual breakthrough. It demonstrates that complex SLS behavior can arise from simple underlying dynamics.
  • Implications for Algorithm Understanding: This work moves beyond simply observing performance to understanding why SLS algorithms behave the way they do, offering a more principled approach to analysis and improvement.

Key Results

  • Irregular RTDs on Specific Instances: For a notable subset of hard Uniform Random-3-SAT instances (especially in the phase transition region), WalkSAT and GWSAT exhibit RTDs that significantly deviate from exponential distributions.
  • Effective Approximation with 2-Component Mixtures: These irregular RTDs can be well approximated by 2-component mixtures of exponential distributions.
  • Trap Instances are Harder: The constructed "plugged combination" instances, designed to contain traps, are demonstrably harder for SLS algorithms than their easy single-solution components, exhibiting irregular RTDs.
  • Markov Chain Model Replicates Behavior: The proposed Markov chain model, particularly the branched version with a trap, generates RTDs that are qualitatively and quantitatively similar to those observed for GWSAT and WalkSAT on irregular instances.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the Markov chain model is a simplification of the complex, multi-dimensional search spaces of SAT problems.
  • While empirical evidence is strong, a formal analytical proof that the Markov chain model's RTDs are always approximable by generalized exponential distributions is still missing.
  • The exact manifestation of "stages" or "plateau regions" in the search space that correspond to the Markov chain states is not fully elucidated.
  • Future Work:
    • Theoretical Analysis of Markov Models: The authors aim to analytically characterize the RTDs of their Markov chain models, rather than relying solely on empirical approximations.
  • Understanding Trap Features: Investigating the connection between traps and other factors known to influence SAT instance hardness (e.g., "backbone robustness") is a key direction.
  • Generalizability: Exploring whether the mixture-model characterization and the trap-based explanation apply to other SLS algorithms for SAT (e.g., WalkSAT/TABU, Novelty+) and even to SLS algorithms for other combinatorial problems (e.g., TSP, MaxSAT).
  • Stagnation on Easier Instances: Investigating if similar mixture RTDs and trap-like phenomena occur when SLS algorithms use non-optimal parameter settings (leading to stagnation).
  • Characterizing Exponential Mixture Conditions: Determining the theoretical conditions under which Markov process RTDs can be characterized by mixtures of exponentials.

Summary updated

BibTeX
@inproceedings{2002mixture,
  title = {{A Mixture-Model for the Behaviour of SLS Algorithms for SAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2002},
}
Figure