Abstract
In formal logic and constraint solving, identifying Maximal Satisfiable Subsets (MSSes) is crucial for diagnosing over-constrained systems. Traditional methods rely on explicit enumeration, which fails when the number of MSSes is large. This paper presents a novel algorithm that reduces MSS counting to projected model counting. This approach enables the counting of trillions of MSSes, a feat previously impossible with enumeration-based tools.
Introduction
When complex systems of rules—such as software specifications or hardware designs—become "unsatisfiable," they contain contradictory constraints. To resolve these conflicts, engineers identify Maximal Satisfiable Subsets (MSSes): the largest groups of rules that can coexist without conflict. However, as systems grow in complexity, the number of possible MSSes can explode exponentially.
The Challenge of MSS Enumeration
For decades, the standard diagnostic approach has been enumeration: finding and listing every single MSS. While useful for small systems, this method hits a "brick wall" when the solution space is vast. If a system has millions or trillions of ways to be "mostly right," an enumerator will attempt to output every single one, leading to timeouts and memory exhaustion. In many diagnostic scenarios, the exact list is less important than the total count, which serves as a metric for system feasibility or repairability.
Methodology: Counting via Projected Models
The authors propose a breakthrough architecture that bypasses enumeration by shifting to a mathematical counting problem. The core idea involves defining a Wrapper ($W$) and a Remainder ($R$).
- Logic Formulation: The set $W$ contains all MSSes plus a set of "extra" satisfiable subsets, while $R$ contains only those extra subsets. The total MSS count is derived as $|W| - |R|$.
- Projected Model Counting: To calculate these sizes, the problem is translated into Boolean formulas. The researchers utilize projected model counting (via the tool GANAK), which counts unique assignments to specific "activation" variables representing active constraints.
- Wrapper Strategies: Four distinct strategies ($W_1$ to $W_4$) were developed to define these wrappers, utilizing techniques like "lean kernels" to prune the search space and logical properties to tighten the bounds.
Experimental Evaluation
The methodology was tested on a benchmark of 1,200 Boolean CNF formulas ranging from 100 to 1,000 clauses. The results demonstrate a significant leap in both coverage and scalability.
As shown in the performance analysis above, the proposed tool solved 510 benchmarks, a substantial improvement over the 353 benchmarks solved by the best existing enumeration-based tools, FLINT and RIME.
The most striking result is the scalability regarding the number of solutions. While traditional enumerators typically fail once the MSS count exceeds $10^6$, the new approach successfully processed instances containing up to $4.74 \times 10^{12}$ (4.7 trillion) MSSes.
Conclusion
By decoupling the counting of solutions from their physical enumeration, this research provides a powerful new tool for analyzing broken systems. While the current implementation faces challenges with extremely large input formulas (thousands of clauses), the shift toward projected model counting opens new avenues for verification in domains like SMT and LTL. Future work will focus on developing "native" counters optimized specifically for the MSS search space.
Summary updated