TL;DR
While top-down search-based counters dominate propositional (CNF) model counting, existing pseudo-Boolean (PB) model counters have relied almost exclusively on bottom-up algebraic decision diagrams (ADDs). This paper presents PBMC, the first exact top-down PB model counter, combining CDCL-style pseudo-Boolean reasoning, component caching with gap saturation, and a new coefficient-aware variable decision heuristic (VCIS). PBMC outperforms state-of-the-art bottom-up PB counters and CNF counters on standard benchmarks.
What Problem Does This Paper Address?
Model counting ($#\text{SAT}$) asks: how many variable assignments satisfy a given logical formula? It is a foundational tool for probabilistic inference, network reliability, and hardware verification.
Traditionally, problems must be flattened into Conjunctive Normal Form (CNF), which often blows up formula size. Pseudo-Boolean (PB) formulas—linear inequalities over Boolean variables (e.g., $\sum a_i x_i \ge k$)—can express complex constraints (such as knapsack capacities or cardinality constraints) much more compactly.
In standard CNF counting, top-down search (using DPLL/CDCL search with component decomposition and caching) vastly outperforms bottom-up compilation (which builds decision diagrams like BDDs or ADDs). Surprisingly, state-of-the-art PB counters (such as PBCount and PBCounter) have followed only the bottom-up paradigm. The authors investigate whether a top-down architecture can work effectively for PB model counting and what domain-specific adaptations it requires.
Methods
The authors introduce PBMC, which integrates techniques from PB solvers (RoundingSat), CNF model counters (GPMC), and PB counting:
- Top-Down Search & Conflict-Driven Learning: PBMC branches on variables, prunes search spaces using learned PB constraints via cutting-plane-style conflict analysis, and splits independent sub-problems into variable-disjoint components.
-
Variable Coefficient Impact Score (VCIS): In PB constraints, some variables carry massive coefficients while others carry small weights. Standard CNF decision heuristics ignore coefficients entirely. VCIS calculates an impact score for variable $x$: $$\frac{1}{|\Omega_x|} \sum_{j \in \Omega_x} \frac{b_x^j}{k_j}$$ where $b_x^j$ is the coefficient of $x$ in constraint $j$, and $k_j$ is the constraint degree. Variables with higher scores have a greater influence on the satisfiability gap and are prioritized.
-
PB Component Caching & Gap Saturation:
- A component is uniquely identified by unassigned variable IDs, unsatisfied constraint IDs, and their remaining satisfiability gaps ($s = k - \sum_{\sigma(\ell)=1} a$).
- Cache Gap Saturation: If the remaining gap $s$ satisfies $0 < s < \min a_j$ (where $\min a_j$ is the smallest coefficient among remaining unassigned literals), setting any remaining literal to true satisfies the constraint. PBMC clamps the cached gap representation to $\min a_j$, merging isomorphic sub-problems and increasing cache hit rates.
Datasets
The authors evaluated PBMC on a standard benchmark suite of 3,500 PB instances (from Yang & Meel, AAAI 2024):
- Auction: 1,000 instances modeling combinatorial auctions.
- M-dim Knapsack: 1,000 instances representing multi-dimensional knapsack problems with diverse coefficients.
- Sensor Placement: 1,500 instances with mostly unit coefficients ($\pm 1$).
- Cost-Aware Sensor Placement: A modified variant introduced by the authors incorporating non-unit coefficients to model sensor costs and redundancy.
Key Insights and Ideas
- Coefficients dictate branching quality: In CNF, all literals in a clause have equal weight. In PB counting, treating literals equally leads to poor branching decisions. Weighting variable decisions by coefficient-to-degree ratios (VCIS) yielded an increase of 115 solved instances in knapsack benchmarks alone.
- Adapting PB solver saturation to caching: In PB solvers, coefficients larger than the right-hand degree are saturated ($a_i \leftarrow k$). In top-down counting, the reverse applies to the gap: if any single variable can satisfy the constraint, different remaining gap values are logically identical and can share a cache entry.
- Top-down excels on non-unit coefficients: On formulas where PB constraints are non-trivial (knapsacks, auctions), top-down PBMC significantly outperformed bottom-up ADDs. On unit-coefficient formulas where constraints behave like clauses, bottom-up counters remain highly competitive.
Key Results
Evaluated on single cores of an AMD EPYC 7713 with a 3,600s timeout:
- Overall Performance: PBMC counted 1,849 instances, beating:
PBCount(bottom-up PB): 1,773 instancesPBCounter(bottom-up PB): 1,508 instancesGanak(state-of-the-art CNF counter): 1,164 instances- Unique Solves: PBMC successfully counted 104 instances that none of the other counters could solve.
- Ablation of VCIS: Replacing VCIS with standard GPMC heuristics dropped solved instances from 1,849 to 1,772.
- Ablation of Cache Saturation: Disabling gap saturation dropped solved instances from 1,849 to 1,844.
- Cost-Aware Sensor Placement: On non-unit sensor placement, PBMC solved 715 instances vs. PBCount's 678.
Limitations and Future Work
- Narrower Lead than in CNF: Top-down PBMC leads bottom-up PBCount by 76 instances (~4%), a much smaller margin than seen between top-down and bottom-up counters in CNF.
- Heuristic Sensitivity: While VCIS helped knapsack instances immensely (+115), it lost 38 instances to GPMC's heuristic on Auction problems. Developing adaptive or portfolio-based decision heuristics is an open need.
- Preprocessing: Top-down CNF counters rely heavily on advanced CNF simplification techniques; top-down PB-specific preprocessors are currently underdeveloped and offer clear room for performance gains.
Summary updated