Disjoint Partial Enumeration without Blocking Clauses

Giuseppe Spallitta, Roberto Sebastiani, Armin BiereAAAI 2024 · DOI

TL;DR

This paper introduces a novel approach for enumerating all possible solutions (models) of a propositional logic formula, specifically focusing on finding disjoint partial models. Their method combines Conflict-Driven Clause Learning (CDCL) with Chronological Backtracking (CB) and a new "implicant shrinking" technique, eliminating the need for computationally expensive blocking clauses. This leads to a more efficient and scalable solution for problems with a large number of solutions.

What Problem Does This Paper Address?

The problem of enumerating all solutions to a propositional formula, known as AllSAT, is crucial for applications in software verification, hardware design, and artificial intelligence. A major challenge is the sheer number of possible solutions, which can grow exponentially with the number of variables. To manage this, researchers often use partial models, which are assignments that don't specify a truth value for every variable, thus representing multiple total assignments simultaneously.

A key distinction is between enumerating solutions with repetitions (AllSAT) and without repetitions (disjoint AllSAT). For many applications, duplicate solutions are problematic. Traditional disjoint AllSAT solvers often rely on adding "blocking clauses" to the formula after each model is found. These clauses prevent the solver from finding the same model again. However, as the number of models increases, so does the number of blocking clauses, which can severely degrade performance due to increased memory usage and slower unit propagation. This paper addresses the inefficiency of blocking clauses by proposing a method for disjoint partial enumeration that avoids them entirely.

Methods

The core of the proposed approach is the integration of three key techniques:

  • Conflict-Driven Clause Learning (CDCL): This standard SAT-solving technique is used to efficiently escape search branches that are guaranteed not to lead to any solutions.
  • Chronological Backtracking (CB): Unlike non-chronological backtracking (which jumps to a specific decision level), CB always backtracks to the most recently assigned decision variable. This ensures that the search space is explored systematically and, crucially, avoids the need for blocking clauses to guarantee disjointness.
  • Implicant Shrinking: This is a novel technique developed by the authors. It aims to reduce the size of partial assignments by identifying literals that can be removed from a found model without affecting its satisfiability, while still ensuring that the resulting partial models remain disjoint. This is achieved by carefully analyzing the decision levels of literals and using a modified 2-watched literal scheme for efficient checking. They propose two variants: a more effective one that dynamically updates watch lists and a faster, more conservative one that avoids this update.

The paper presents algorithms for conflict analysis (Algorithm 2) and assignment analysis (Algorithm 3), which incorporate these techniques. Notably, their conflict analysis handles chronological backtracking, and their assignment analysis uses implicant shrinking to produce compact partial models.

Datasets

The paper evaluates their approach using the following benchmarks:

  • Binary clauses: A crafted dataset designed to have a large number of solutions.
  • Rnd3sat: Random 3-SAT problems generated by the authors, with a specific clause-to-variable ratio suitable for AllSAT.
  • CSB (1000): A benchmark set.
  • BMS (500): A benchmark set.
  • SATLIB benchmarks: Specifically, CBS and BMS instances from the SATLIB repository.

The authors note that many standard SAT benchmarks are not well-suited for AllSAT due to having few or no solutions, or being encoded in a way that prevents effective partial model generation.

Key Insights and Ideas

  • Blocking clauses are the bottleneck: The paper clearly demonstrates that the exponential growth of blocking clauses is a major performance limiter in traditional disjoint AllSAT solvers.
  • Chronological Backtracking is key to disjointness without blocking: By strictly adhering to chronological backtracking, the solver naturally avoids revisiting previously found models, thus eliminating the need for explicit blocking clauses.
  • Implicant shrinking is crucial for partial models: To generate compact partial models efficiently, a specialized implicant shrinking technique is required that is compatible with chronological backtracking and guarantees disjointness.
  • A faster, conservative implicant shrinking works well: While dynamically updating watch lists is more effective at shrinking assignments, the simpler, faster variant of implicant shrinking provides better overall performance, especially when dealing with many solutions.
  • Virtual backtrack reason clauses: To handle the need for reason clauses in CDCL when combined with CB, the authors propose a "virtual" approach that reconstructs these clauses on the fly, saving memory and avoiding complex clause management.

Key Results

The paper's proposed tool, TABULARALLSAT, which implements their novel approach, demonstrates significant improvements over existing solvers:

  • Higher Instance Solved: TABULARALLSAT solves the highest number of instances across most benchmark sets compared to BDD, NBC, BC, and MathSAT. For example, it solves 1939 out of 1960 total instances, compared to 1935 for BDD and 1915 for NBC.
  • Competitive Performance: While BDD performs better on RND3SAT instances (attributed to their structure being easily compiled into BDDs), TABULARALLSAT is competitive or superior on other benchmarks.
  • Efficiency of Implicant Shrinking: Figure 1 shows that the "light-check" (faster, conservative) implicant shrinking algorithm achieves comparable results in terms of CPU time and number of partial models to the more complex "watch-list-shrinking" variant.
  • Outperforms Blocking Solvers: The experimental results (Table 1 and Figure 2) consistently show TABULARALLSAT outperforming blocking solvers (BC, BC_PARTIAL) and non-blocking solvers (NBC) in terms of the number of solved instances and CPU time.

Limitations and Future Work

  • RND3SAT performance: TABULARALLSAT is outperformed by BDD on RND3SAT instances. The authors suggest this is due to the specific structure of these instances being amenable to BDD compilation.
  • Knowledge Compilation: The authors mention that knowledge compilation techniques (like D4) could be explored, although they note that compilation itself can be a costly preprocessing step and is not an "any-time" approach.
  • Novel Decision Heuristics: They plan to investigate new decision heuristics specifically tailored for chronological backtracking to further improve TABULARALLSAT's performance.
  • Projected Enumeration: Extending their techniques to handle "projected enumeration" (finding solutions for a subset of variables) is a future direction.
  • Component Caching: Integrating chronological backtracking with component caching is another avenue for future research.

Summary updated

BibTeX
@inproceedings{spallitta2024disjoint,
  author = {Giuseppe Spallitta and Roberto Sebastiani and Armin Biere},
  title = {{Disjoint Partial Enumeration without Blocking Clauses}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i8.28652},
}
Figure