Abstract: All Solution SAT (AllSAT) is a variant of Propositional Satisfiability, which aims to find all satisfying assignments for a given formula. AllSAT has significant applications in different domains, such as software testing, data mining, and network verification. In this paper, observing that the lack of component analysis may result in more work for algorithms with non-chronological backtracking, we propose a DPLL-based algorithm for solving AllSAT problem, named AllSATCC, which takes advantage of component analysis to reduce work repetition caused by non-chronological backtracking. The experimental results show that our algorithm outperforms the state-of-the-art algorithms on most instances.
Introduction: The Challenge of AllSAT
Propositional Satisfiability (SAT) usually asks if there is any way to make a formula true. AllSAT asks a much harder question: "What are all the ways to make this formula true?" This is critical for applications like software testing (generating all possible test cases), data mining, and network verification.
Modern SAT solvers use a technique called non-chronological backtracking (NCB). When they hit a dead end, they "jump back" several levels in the search tree to fix the root cause of the conflict. While NCB makes standard SAT solvers incredibly fast, it creates a "memory loss" problem for AllSAT solvers. When the solver jumps back, it often erases satisfying assignments it already found for independent parts of the formula, forcing it to solve the same sub-problems over and over again.
Methods
The authors propose AllSATCC, a solver built on the DPLL (Davis-Putnam-Logemann-Loveland) framework that specifically targets this "work repetition" issue. Its core innovations include:
- Dynamic Component Extraction: The solver views the formula as a "constraint graph" to identify independent sub-problems (components) that don't share variables. By solving these separately, it can combine their results mathematically rather than searching every possible combination.
- Component Caching: Once a sub-problem is solved, the result is stored in a cache. If the solver encounters that same sub-problem again after a backtrack, it pulls the answer from memory instead of re-calculating it.
- Partial Assignment Generation: To keep the output manageable, the solver identifies "irrelevant" or "implied" variables. Instead of listing every single full assignment, it provides "partial assignments" that represent large sets of solutions compactly.
- Conflict-Driven Learning: It retains the power of modern SAT solvers by using clause learning to prune the search space, while managing the interaction between learning and components to ensure no solutions are lost.
Experimental Results
The authors evaluated AllSATCC against four baseline solvers (BASolver, BC, NBC, and BDD) using a massive suite of 501 CNF benchmarks including real-world instances from SAT Competitions, SATLIB graph coloring problems, and circuit-based benchmarks.
Key Findings
- Superior Coverage: AllSATCC solved 467 out of 501 benchmarks within the time limit, significantly more than the next best solver, BDD (384) and NBC (252).
- Speed on Hard Instances: On the
Flatinstances from SATLIB—which are notoriously difficult for AllSAT—AllSATCC solved every instance in under 100 seconds, while some competitors couldn't solve a single one. - Scalability: As the number of satisfying assignments grew (from $10^4$ to over $10^{13}$), AllSATCC’s performance advantage became even more pronounced compared to BDD-based and blocking solvers.
Conclusion
AllSATCC demonstrates that component analysis is the essential "bridge" that allows non-chronological backtracking to work in AllSAT without destroying previous progress. While component analysis adds some computational overhead, the savings in redundant search time make it highly effective for complex, real-world formulas. Future work will focus on more sophisticated component selection heuristics and further optimizing memory management for caching.
Summary updated