Component Caching in Hybrid Domains with Piecewise Polynomial Densities


  • Vaishak Belle KU Leuven
  • Guy Van den Broeck University of California, Los Angeles
  • Andrea Passerini University of Trento



model counting, probabilistic inference, hybrid graphical models


Counting the models of a propositional formula is an important problem: for example, it serves as the backbone of probabilistic inference by weighted model counting. A key algorithmic insight is component caching (CC), in which disjoint components of a formula, generated dynamically during a DPLL search, are cached so that they only have to be solved once. In the recent years, driven by SMT technology and probabilistic inference in hybrid domains, there is an increasing interest in counting the models of linear arithmetic sentences. To date, however, solvers for these are block-clause implementations, which are nonviable on large problem instances. In this paper, as a first step in extending CC to hybrid domains, we show how propositional CC systems can be leveraged when limited to piecewise polynomial densities. Our experiments demonstrate a large gap in performance when compared to existing approaches based on a variety of block-clause strategies.




How to Cite

Belle, V., Van den Broeck, G., & Passerini, A. (2016). Component Caching in Hybrid Domains with Piecewise Polynomial Densities. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1).



Technical Papers: Search and Constraint Satisfaction