Improving Model Counting by Leveraging Definability

Jean-Marie Lagniez, Emmanuel Lonca, Pierre MarquisIJCAI 2016

Abstract

Propositional model counting (#SAT) is a fundamental problem in artificial intelligence with applications ranging from probabilistic inference to hardware reliability. However, its #P-complete nature makes it computationally intensive. This paper introduces B + E, a novel preprocessing technique that leverages logical definability to simplify formulas. By identifying and eliminating variables implicitly determined by others, B + E significantly enhances the performance of state-of-the-art model counters, enabling them to solve a larger number of complex instances within practical time limits.

Introduction

The task of propositional model counting (#SAT) involves determining the number of satisfying assignments for a given Boolean formula. While essential for many AI domains, it is significantly more challenging than the standard SAT problem. To mitigate this complexity, researchers employ preprocessors to simplify formulas before they reach the main solver. Traditional preprocessing methods often rely on explicit gate detection (e.g., identifying AND/OR structures) to remove redundant variables. However, the vast space of possible logical dependencies makes exhaustive gate detection infeasible. This work addresses this limitation by focusing on the broader concept of logical definability.

Methodology: The B + E Preprocessor

The proposed B + E approach consists of two primary phases:

  1. B (Bipartition): This phase identifies "defined" variables—those whose values are uniquely determined by a subset of other variables. Utilizing Padoa’s Theorem and a SAT solver, the preprocessor checks for implicit definability. Unlike previous methods, it does not require knowledge of the specific logical gate; it merely confirms that a functional dependency exists.
  2. E (Elimination): Once defined variables are identified, they are systematically eliminated from the formula. This "forgetting" process preserves the total model count. To manage formula size and complexity during elimination, the authors incorporate techniques such as vivification and occurrence simplification.

The core strength of B + E lies in its ability to detect complex dependencies that traditional gate-based methods overlook, relying on Beth’s Theorem to guarantee that an explicit definition exists if an implicit one is found.

Experimental Evaluation

The effectiveness of B + E was evaluated using a diverse set of 703 CNF instances from the SATLIB repository, including benchmarks from Bayesian networks (BN), hardware circuits, AI planning, and quantitative information flow (Qif). The performance of B + E was compared against the existing state-of-the-art preprocessor, pmc, across three prominent model counters: Cachet, SharpSAT, and C2D.

Cactus plot showing the number of instances solved over time for various solvers and preprocessors.

Results and Discussion

The experimental results demonstrate that B + E provides a substantial performance boost across multiple dimensions:

  • Enhanced Solvability: As shown in the cactus plot, B + E allows solvers to handle significantly more instances within a one-hour timeout. For example, the Cachet solver's capacity increased from 558 solved instances with pmc to 602 with B + E.
  • Superior Compression: B + E consistently achieves greater reductions in the number of variables (#var) and literals (#lit) compared to pmc. This is particularly evident in structured domains like Planning and Bayesian Networks.
  • Computational Efficiency: Despite the overhead of multiple SAT solver calls during the B phase, the resulting formula simplification often leads to a net reduction in total processing time. In many instances, the simplified formula becomes trivial for the downstream counter.
Scatter plots comparing B+E and pmc across variable/literal reduction and solver execution time.

Conclusion

The B + E preprocessor represents a significant advancement in #SAT solving by shifting the focus from explicit gate detection to general logical definability. While highly effective, future work could refine the heuristics used to select variables for definability testing to further reduce preprocessing overhead. Additionally, applying these definability-based techniques to related problems like Projected Model Counting offers a promising avenue for further research.

Summary updated

BibTeX
@inproceedings{lagniez2016improving,
  author = {Jean-Marie Lagniez and Emmanuel Lonca and Pierre Marquis},
  title = {{Improving Model Counting by Leveraging Definability}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure