Projected Model Counting (PMC) is a critical task in automated reasoning, particularly for assessing the robustness of AI plans and verifying complex hardware designs. While standard model counting (#SAT) determines the total number of satisfying assignments for a Boolean formula, PMC focuses on counting unique assignments over a specific subset of variables. This paper introduces projMC, a recursive algorithm that employs a novel disjunctive decomposition scheme to tackle this #P-hard problem efficiently.
Introduction
In many real-world applications, we are interested in the number of models of a formula $\Sigma$ after projecting them onto a subset of variables $P$. Mathematically, this corresponds to counting the models of $\exists (V \setminus P). \Sigma$, where $V$ is the set of all variables. This task is significantly harder than standard #SAT because traditional variable elimination techniques often lead to an exponential explosion in formula size.
Existing approaches to PMC typically fall into two categories: compilation-based methods, which transform the formula into a tractable representation like d-DNNF, and blocking-clause methods, which iteratively find and block models. However, these methods often struggle with scalability. projMC addresses these limitations by using a direct recursive search guided by formula decomposition.
The projMC Algorithm
The efficiency of projMC stems from three primary algorithmic pillars:
- Disjunctive Decomposition: This is the primary innovation of the paper. Instead of simple variable branching, the algorithm identifies a single model of the formula. This model is used to define a "core" sub-problem where the variables to be projected out are effectively handled. The algorithm then recursively solves for this core and its negation.
- Conjunctive (Component) Decomposition:
projMCidentifies disjoint components within the formula—sub-problems that do not share any variables. By solving these components independently and multiplying their results, the algorithm significantly reduces the search space. - Caching: To avoid redundant computations,
projMCutilizes a cache to store and retrieve results for previously encountered sub-problems.
When the recursion reaches a state where no variables to be projected out remain, the problem reduces to standard model counting, which is handled by the high-performance counter D4.
Experimental Evaluation
The authors evaluated projMC against four state-of-the-art solvers: D4P, dSharpP, #clasp, and d2c. The benchmark suite consisted of 260 instances:
- Random 3-CNF Formulae (100 instances): Standard benchmarks with varying difficulty.
- Random Boolean Circuits (60 instances): Simulating logic gate structures.
- Planning Instances (100 instances): Derived from classical AI planning domains such as "Logistics" and "Rovers," where PMC is used to measure plan robustness.
Experiments were conducted with a 600-second timeout and a 4GB memory limit per instance.
Key Results
The empirical results demonstrate the clear superiority of projMC over existing tools. As shown in the cactus plot below, projMC solved significantly more instances within the time limit than any other solver.
Specifically, projMC solved 192 instances, while the next best solver, D4P, solved only 140. Furthermore, projMC was the only solver capable of finishing 44 of the instances in the benchmark set.
The head-to-head comparisons in the scatter plots below further highlight the performance gap. In many cases, projMC achieved speedups of several orders of magnitude, particularly on planning and random instances.
While projMC dominated most categories, D4P remained competitive on certain circuit-based instances. This suggests that while recursive decomposition is highly effective, there is still room for specialized techniques in specific domains.
Conclusion
projMC represents a significant advancement in projected model counting. By combining disjunctive and conjunctive decomposition with efficient caching, it provides a robust and scalable solution for a variety of complex reasoning tasks. Future work includes integrating advanced preprocessing techniques, such as gate detection, and extending the algorithm to support knowledge compilation into d-DNNF representations.
Summary updated