An Improved Decision-DNNF Compiler

Jean-Marie Lagniez, Pierre MarquisIJCAI 2017 · DOI

TL;DR

This paper introduces D4, a new compiler that generates Decision-DNNF representations of propositional logic formulas. D4 significantly outperforms existing compilers like C2D and Dsharp in both compilation time and the size of the generated representations, making knowledge compilation more efficient.

What Problem Does This Paper Address?

Knowledge compilation (KC) is a crucial technique for tackling complex reasoning problems that are intractable with standard propositional representations. The goal of KC is to transform these problems into a more manageable form, often a specialized circuit-like structure, that allows for faster querying. However, the process of compiling these representations can itself be computationally expensive, and the resulting compiled forms can be very large, limiting their practical applicability. This paper addresses the challenge of creating more efficient compilers that produce smaller and faster-to-generate compiled representations, specifically in the Decision-DNNF language.

Methods

D4 is a top-down, tree-search compiler that builds Decision-DNNF representations. It builds upon existing techniques like disjoint component analysis, conflict analysis, and non-chronological backtracking, which are common in state-of-the-art compilers like C2D and Dsharp.

What's novel about D4 lies in its dynamic decomposition approach and its parsimonious use of hypergraph partitioning. Unlike C2D, which pre-computes a decomposition tree, D4 computes decompositions dynamically during the search. Similar to Dsharp, it uses a dynamic approach but differs in how it guides the decomposition. D4 partitions the dual hypergraph of the input formula under the current partial assignment.

Key improvements include:

  • Parsimonious Hypergraph Partitioning: D4 avoids calling the computationally expensive hypergraph partitioning (HGP) at every step. It only performs HGP when certain conditions are met (e.g., the variable list is empty or a significant number of propagations are achieved).
  • Hypergraph Simplification Rules: D4 employs specific rules to simplify the hypergraph before partitioning. This reduces the size of the hypergraph and can lead to better decompositions, ultimately improving the quality of the compiled output and reducing the time spent in partitioning.
  • Improved SAT Solver: D4 utilizes a more recent SAT solver (based on MiniSAT 2.2) compared to those used in C2D and Dsharp, which contributes to its efficiency.

Datasets

The authors evaluated D4 on 703 CNF instances from the SAT Library (www.cs.ubc.ca/~hoos/SATLIB/index-ubc.html), categorized into 8 datasets: BN (Bayesian networks), BMC (Bounded Model Checking), Circuit, Configuration, Handmade, Planning, Random, and Qif (Quantitative Information Flow analysis - security).

Key Insights and Ideas

  • Dynamic Decomposition with Sparsity is Key: The core insight is that a dynamic decomposition approach, guided by hypergraph partitioning but used sparingly and enhanced with simplification rules, leads to significant improvements over static or brute-force dynamic methods.
  • Hypergraph Simplification Pays Off: The specific simplification rules designed for hypergraphs are crucial. They not only speed up the partitioning process but also improve the quality of the resulting decompositions, leading to smaller compiled forms.
  • Solver Choice Matters, but Isn't Everything: While using a more modern SAT solver contributes to D4's performance, the experimental results suggest that the compiler's specific decomposition heuristics and simplification strategies are the primary drivers of its superiority over C2D and Dsharp.
  • Efficiency Gains are Substantial: The paper demonstrates that D4 can achieve dramatic reductions in both compilation time and, more importantly, the size of the Decision-DNNF representations, often by orders of magnitude.

Key Results

  • Compilation Time: D4's compilation times are significantly lower than C2D and Dsharp on many instances.
  • Size of Representations: The Decision-DNNF representations generated by D4 are substantially smaller than those produced by C2D and Dsharp for the vast majority of instances.
  • Instance Solvability: D4 solved 574 out of 703 instances within the given time and memory limits, outperforming C2D (546 instances) and Dsharp (467 instances).
  • Model Counting Performance: D4 also shows competitive performance as an exact model counter, though it incurs some computational overhead for generating the compiled form.

Limitations and Future Work

  • Computational Overhead of PaToH: The paper acknowledges that hypergraph partitioning (PaToH) is computationally intensive, consuming at least 50% of D4's total computation time for many instances. While D4 mitigates this by using it sparingly, it remains a bottleneck.
  • No Simplification of Final Representations: D4 does not apply reduction rules to the final Decision-DNNF representations, meaning the reported sizes are for uncompressed forms. Future work could explore applying such rules.
  • Further Optimization of Decomposition Heuristics: While D4's heuristics are effective, there's always room for improvement in finding even better decomposition strategies.
  • Comparison with Other Languages: The paper focuses on Decision-DNNF. Extending these techniques to other knowledge compilation languages could be a valuable future direction.

Summary updated

BibTeX
@inproceedings{lagniez2017improved,
  author = {Jean-Marie Lagniez and Pierre Marquis},
  title = {{An Improved Decision-DNNF Compiler}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/93},
}
Figure