Locality in Random SAT Instances

Jesús Giráldez-Cru, Jordi LevyIJCAI 2017 · DOI

TL;DR

This paper introduces a novel random SAT instance generator, the Popularity-Similarity (PS) model, that captures both the scale-free structure (power-law distribution of variable occurrences) and the locality (similarity between variables) observed in real-world industrial SAT problems. This new model helps explain why modern CDCL SAT solvers, like VSIDS, are so effective on these complex instances, as they leverage both popularity and similarity for efficient search.

What Problem Does This Paper Address?

Despite the remarkable success of Conflict-Driven Clause Learning (CDCL) SAT solvers on industrial problems, there's a persistent gap in understanding why they perform so well. While CDCL solvers have evolved significantly, the underlying structure of the SAT instances they tackle remains a key area of research. Industrial SAT instances exhibit specific structural properties, such as a power-law distribution in variable occurrences (meaning a few variables appear very frequently) and a notion of "locality" or "similarity" where related variables tend to cluster. Existing random SAT instance generators often capture one of these properties but not both simultaneously. This makes it difficult to create benchmarks that truly mimic the complexity and structure of real-world problems, hindering a deeper analysis of solver behavior and the development of more effective solving strategies. This paper aims to bridge this gap by proposing a generator that captures both scale-free structure and locality, providing a more realistic testbed for SAT solvers.

Methods

The authors propose the Popularity-Similarity (PS) model for generating random SAT instances. This model builds upon existing work in complex networks and random graph generation. Key aspects include:

  • Bi-partite Graph Construction: A graph is constructed with two sets of nodes: variables and clauses. Edges represent the occurrence of a variable in a clause.
  • Probability of Edge Selection: The probability of an edge between a variable node i and a clause node j is defined by a function that incorporates:
  • Popularity: Modeled by a term proportional to log(i) for variables and log(j) for clauses.
  • Similarity: Modeled by the angular distance between randomly assigned angles for variables and clauses (θij).
  • Temperature (T): A parameter that controls the randomness. High temperatures lead to more random choices, while low temperatures emphasize popularity and similarity.
  • Fermi-Dirac Distribution: The edge selection probability is inspired by the Fermi-Dirac distribution, commonly used in physics for particles with constraints. This allows for a controlled generation of edges based on an "energy" function that combines popularity and similarity.
  • Scale-Free and Community Structure: The model is designed to generate instances with a power-law distribution of variable occurrences (scale-free) and a notion of locality that leads to community structure.
  • Clause Size Distribution: The model also generates clauses with varying sizes, following a power-law distribution, which is another characteristic of industrial instances.

The authors also detail methods for normalizing the probability distribution and approximating parameters, including using the Newton-Raphson method.

Datasets

The paper does not use pre-existing datasets. Instead, it introduces a new benchmark generation methodology: the Popularity-Similarity (PS) model. This model allows for the creation of synthetic SAT instances with controlled structural properties (popularity, similarity, scale-free nature, clause size distribution) by varying parameters like β, β', and T. These generated instances are then used to evaluate SAT solver performance.

Key Insights and Ideas

  • Locality is Crucial for CDCL Solvers: The paper strongly suggests that the "locality" or "similarity" of variables in SAT instances is as important as their "popularity" (frequency of occurrence) for the effectiveness of modern CDCL solvers.
  • VSIDS Exploits Both: The Variable State Independent Decaying Sum (VSIDS) heuristic, a core component of many CDCL solvers, is shown to effectively leverage both variable popularity and similarity. It focuses on popular variables and also on variables that are "close" in some sense (similar).
  • Explaining Solver Success: The PS model provides a theoretical framework to explain why CDCL solvers excel on industrial SAT problems. Their success is not just due to speed but their ability to exploit these specific structural properties.
  • Phase Transition Behavior: The PS model exhibits a SAT-UNSAT phase transition, similar to classical random SAT models, which is desirable for generating challenging instances.
  • Orthogonal Forces: Popularity and similarity are presented as two distinct, yet complementary, forces that solvers can exploit.

Key Results

  • Empirical Evidence for VSIDS: Experiments using the Minisat solver (which employs VSIDS) demonstrate that when formulas have high popularity or high similarity, VSIDS focuses its decisions accordingly. In formulas with both properties, the solver finds a good balance.
  • CDCL vs. Other Solvers: CDCL solvers (like Glucose) significantly outperform other types of solvers (like look-ahead solver March) on PS instances with low temperatures (i.e., high popularity and similarity). Conversely, when the temperature is high (making instances more random), the performance gap narrows or reverses.
  • Impact of Temperature: As temperature increases in the PS model, instances become harder for CDCL solvers until a very high temperature is reached, at which point they become easier for solvers like March, behaving more like classical random SAT instances.
  • Scale-Free and Clause Size Properties: The PS model successfully generates instances with power-law distributions for both variable occurrences and clause sizes, with exponents related to the model's parameters (β and β').

Limitations and Future Work

  • Analytical Calculation of R: The paper notes that analytically computing the normalizing constant R for all temperature values is difficult, requiring numerical methods like Newton-Raphson.
  • Simplification of Model: While the Fermi-Dirac distribution is theoretically grounded, a simplified version is also explored for practical generation.
  • Focus on 3-CNF: The experimental evaluation primarily focuses on 3-CNF instances (clauses of size 3) to isolate the effects of popularity and similarity, though the model can generate clauses of varying sizes.
  • Future Work: The authors suggest that understanding the interplay of popularity and similarity is crucial for developing new SAT solving techniques and for designing more realistic random SAT instance generators. Further investigation into the theoretical properties of the PS model, especially concerning its phase transition and hardness, is also implied.

Summary updated

BibTeX
@inproceedings{giraldezcru2017locality,
  author = {Jesús Giráldez-Cru and Jordi Levy},
  title = {{Locality in Random SAT Instances}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/89},
}
Figure