Disjoint Projected Enumeration for SAT and SMT without Blocking Clauses
For practitioners in formal verification and AI, this work addresses memory blowups and inefficiencies in AllSAT/AllSMT enumeration, offering more efficient solvers for tasks like test generation and model checking.
The paper introduces tabularAllSAT and tabularAllSMT, novel solvers for AllSAT and AllSMT that combine CDCL with chronological backtracking and an aggressive implicant shrinking algorithm to achieve disjoint enumeration without blocking clauses. Experimental results show superiority over state-of-the-art solvers, especially in projected enumeration and SMT-based reasoning scenarios.
All-Solution Satisfiability (AllSAT) and its extension, All-Solution Satisfiability Modulo Theories (AllSMT), have become more relevant in recent years, mainly in formal verification and artificial intelligence applications. The goal of these problems is the enumeration of all satisfying assignments of a formula (for SAT and SMT problems, respectively), making them useful for test generation, model checking, and probabilistic inference. Nevertheless, traditional AllSAT algorithms face significant computational challenges due to the exponential growth of the search space and inefficiencies caused by blocking clauses, which cause memory blowups and degrade unit propagation performances in the long term. This paper presents two novel solvers: tabularAllSAT, a projected AllSAT solver, and tabularAllSMT, a projected AllSMT solver. Both solvers combine Conflict-Driven Clause Learning (CDCL) with chronological backtracking to improve efficiency while ensuring disjoint enumeration. To retrieve compact partial assignments we propose a novel aggressive implicant shrinking algorithm, compatible with chronological backtracking, to minimize the number of partial assignments, reducing overall search complexity. Furthermore, we extend the solver framework to handle projected enumeration and SMT formulas effectively and efficiently, adapting the baseline framework to integrate theory reasoning and the distinction between important and non-important variables. An extensive experimental evaluation demonstrates the superiority of our approach compared to state-of-the-art solvers, particularly in scenarios requiring projection and SMT-based reasoning.