Abstract
Pseudo-Boolean model counting involves computing the number of satisfying assignments of a given pseudo-Boolean (PB) formula. In recent years, PB model counting has seen increased interest partly owing to the succinctness of PB formulas over typical propositional Boolean formulas in conjunctive normal form (CNF) at describing problem constraints. In particular, the research community has developed tools to tackle exact PB model counting. These recently developed counters follow one of the two existing major designs for model counters, namely the bottom-up model counter design. A natural question would be whether the other major design, the top-down model counter paradigm, would be effective at PB model counting, especially when the top-down design offered superior performance in CNF model counting literature. In this work, we investigate the aforementioned top-down design for PB model counting and introduce the first exact top-down PB model counter, PBMC. PBMC is a top-down search-based counter for PB formulas, with a new variable decision heuristic that considers variable coefficients. Through our evaluations, we highlight the superior performance of PBMC at PB model counting compared to the existing state-of-the-art counters PBCount, PBCounter, and Ganak. In particular, PBMC could count for 1849 instances while the next-best competing method, PBCount, could only count for 1773 instances, demonstrating the potential of a top-down PB counter design.
Introduction
Model counting is a fundamental task in automated reasoning, focused on determining the number of satisfying assignments for a set of logical constraints. While much of the literature has historically focused on formulas in Conjunctive Normal Form (CNF), many complex real-world problems—ranging from resource allocation to sensor placement—are more naturally expressed as Pseudo-Boolean (PB) formulas. These formulas take the form of linear inequalities with binary variables, such as $3x_1 + 2x_2 - x_3 \ge 2$, allowing for a more succinct representation than traditional Boolean logic.
Despite the expressive power of PB formulas, the development of exact PB model counters has lagged behind CNF counters. Existing PB counters have primarily relied on "bottom-up" architectures, which utilize Algebraic Decision Diagrams (ADDs) to build solutions from the ground up. However, in the realm of CNF counting, "top-down" search-based methods have long been the dominant paradigm due to their efficiency in handling large-scale problems. This research introduces PBMC, the first exact top-down PB model counter, bridging the gap between PB logic and high-performance search-based counting techniques.
Methodology
PBMC adapts the top-down search framework—traditionally used for CNF—to the specific requirements of Pseudo-Boolean constraints. The system incorporates three primary innovations:
1. Top-Down Search with CDCL
PBMC utilizes a search-based algorithm inspired by Conflict-Driven Clause Learning (CDCL). The solver recursively assigns values to variables, simplifies the remaining formula, and decomposes the problem into independent sub-problems (components). These components are solved individually, and their results are combined to determine the total model count.
2. Variable Coefficient Impact Score (VCIS)
A critical challenge in top-down counting is the variable ordering heuristic. In standard CNF, variables are often treated with equal weight. In PB formulas, however, variables with larger coefficients have a disproportionate impact on whether a constraint is satisfied. PBMC introduces the VCIS heuristic, which prioritizes branching on variables with high coefficient impact. This allows the solver to satisfy or falsify constraints more rapidly, pruning the search space significantly.
3. Advanced Component Caching and Gap Saturation
To prevent redundant computations, PBMC caches the results of previously solved sub-problems. The authors introduced a "gap saturation" optimization to improve cache hit rates. This technique recognizes functional symmetries: if a constraint is "nearly satisfied" such that any further valid assignment will push it over the required threshold, the solver treats these functionally equivalent states as identical in the cache. This allows the solver to skip massive branches of the search tree that would otherwise be re-evaluated.
Experimental Evaluation
The performance of PBMC was evaluated against a benchmark of 3,500 instances across three domains: combinatorial auctions, multi-dimensional knapsack problems, and sensor placement. These benchmarks represent standard challenges in the field and provide a rigorous test for model counting efficiency.
PBMC was compared against the current state-of-the-art PB counters, PBCount and PBCounter, as well as Ganak, a leading CNF model counter. The results demonstrate a clear advantage for the top-down approach:
- Total Solved Instances: PBMC successfully solved 1,849 instances within the 3,600-second timeout.
- Competitive Margin: PBMC outperformed PBCount (1,773 instances), PBCounter (1,508 instances), and Ganak (1,164 instances).
- Heuristic Efficacy: The VCIS heuristic proved essential; a version of PBMC using standard CNF heuristics solved 77 fewer instances, highlighting the importance of coefficient-aware decision-making.
While PBMC dominated the Auction and Knapsack categories, it performed slightly behind PBCount in the Sensor Placement domain, suggesting that the structure of specific problem types may still favor bottom-up approaches in limited cases.
Conclusion and Future Work
The introduction of PBMC demonstrates that the top-down search paradigm is highly effective for Pseudo-Boolean model counting, challenging the previous dominance of bottom-up ADD-based methods. By leveraging coefficient-aware heuristics and optimized component caching, PBMC sets a new state-of-the-art for the field.
Future research will focus on refining PB-specific preprocessing techniques and exploring tree decomposition to further enhance search efficiency. As a prototype, PBMC lays the groundwork for a new generation of solvers capable of handling the complex, succinct constraints found in modern optimization and verification problems.
Summary updated