An Exhaustive DPLL Algorithm for Model Counting

Umut Oztok, Adnan DarwicheJAIR 2018 · DOI

Introduction

Model counting, or #SAT, is the fundamental task of determining the number of satisfying assignments for a given logical formula. As a #P-complete problem, it serves as the computational backbone for diverse fields such as artificial intelligence planning, probabilistic reasoning, and risk analysis. While high-performance model counters like sharpSAT and c2d exist, they often operate as "black boxes"—highly optimized but lacking formal semantics. This lack of transparency makes it difficult to verify their correctness or to integrate new SAT-solving advancements seamlessly.

In this work, Umut Oztok and Adnan Darwiche present a significant advancement: a modular, exhaustive DPLL algorithm for model counting. Their approach, implemented in the miniC2D system, bridges the gap between high-performance search and formal knowledge compilation.

Methodology

The researchers introduced a system built on three primary pillars designed to enhance both the flexibility and the theoretical grounding of model counting.

Modular Interface

To move away from monolithic designs, the authors defined a formal "SAT State" and a set of primitive operations, or macros. This modularity allows the core counting algorithm to treat the underlying SAT solver as a plug-in component. By standardizing how decisions are made, undone, and asserted, the system can incorporate various SAT technologies without altering the counting logic.

Formal macros defining the modular interface for SAT state manipulation.

Decision Vtrees and Component Analysis

The algorithm utilizes a control structure known as a "vtree" to guide static component analysis. This technique identifies independent sub-problems within a formula, enabling the counter to solve them separately and multiply their results—a classic "divide and conquer" strategy that is essential for handling large-scale problems.

A decision vtree structure used to guide the search and identify independent components.

Top-Down Compilation

The most significant theoretical contribution is the realization that the search "trace" of their algorithm is a valid Sentential Decision Diagram (SDD). By recording this trace, the authors created the first "top-down" SDD compiler. Unlike traditional "bottom-up" methods that synthesize SDDs from small fragments, this approach allows the search process itself to carve out the structure, leading to massive efficiency gains.

Experimental Evaluation

The authors evaluated miniC2D using a comprehensive suite of benchmarks, including 1392 CNF instances from the CRIL repository and circuit benchmarks from iscas85, iscas89, and LGSynth89. They compared their system against state-of-the-art counters: cachet, c2d, and sharpSAT.

Key Results

The experimental results highlight the power of the top-down approach:

  • Competitive Performance: miniC2D solved 1042 instances, performing comparably to state-of-the-art counters and even solving 12 instances that no other counter could handle.
  • Compilation Speedups: The top-down SDD compiler achieved orders-of-magnitude improvements in construction time. In 40 out of 61 benchmark cases, it was at least 10x faster than the best bottom-up compiler.
  • Formal Verification: The modular design enabled the first formal proof of correctness for such a complex counting system, providing a level of reliability previously unavailable in high-performance solvers.

Conclusion

By unifying search-based counting and structure-based compilation, this research provides a robust framework for future developments in automated reasoning. While the current implementation relies on static component analysis, the modular architecture of miniC2D paves the way for integrating dynamic analysis and advanced conflict-driven clause learning (CDCL) optimizations, further pushing the boundaries of what is possible in model counting and knowledge compilation.

Summary updated

BibTeX
@article{oztok2018exhaustive,
  author = {Umut Oztok and Adnan Darwiche},
  title = {{An Exhaustive DPLL Algorithm for Model Counting}},
  journal = {J. Artif. Intell. Res.},
  year = {2018},
  doi = {10.1613/jair.1.11201},
}
Figure