An ADD-based symbolic Ryser algorithm computes permanents of dense and similar-row matrices up to size 70-80, outperforming CNF-based exact counters and explicit Ryser on these instances.
ADDMC: Weighted Model Counting with Algebraic Decision Diagrams
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We present an algorithm to compute exact literal-weighted model counts of Boolean formulas in Conjunctive Normal Form. Our algorithm employs dynamic programming and uses Algebraic Decision Diagrams as the primary data structure. We implement this technique in ADDMC, a new model counter. We empirically evaluate various heuristics that can be used with ADDMC. We then compare ADDMC to state-of-the-art exact weighted model counters (Cachet, c2d, d4, and miniC2D) on 1914 standard model counting benchmarks and show that ADDMC significantly improves the virtual best solver.
fields
cs.DS 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On Symbolic Approaches for Computing the Matrix Permanent
An ADD-based symbolic Ryser algorithm computes permanents of dense and similar-row matrices up to size 70-80, outperforming CNF-based exact counters and explicit Ryser on these instances.