Compiling Constraint Networks into Multivalued Decomposable Decision Graphs
Abstract
We present and evaluate a top-down algorithm for compiling finite-domain constraint networks (CNs) into the language MDDG of multivalued decomposable decision graphs. Though it includes Decision-DNNF as a proper subset, MDDG offers the same key tractable queries and transformations as Decision-DNNF, which makes it useful for many applications. Intensive experiments showed that our compiler cn2mddg succeeds in compiling CNs which are out of the reach of standard approaches based on a translation of the input network to CNF, followed by a compilation to Decision-DNNF. Furthermore, the sizes of the resulting compiled representations turn out to be much smaller (sometimes by several orders of magnitude).
Cite
Text
Koriche et al. "Compiling Constraint Networks into Multivalued Decomposable Decision Graphs." International Joint Conference on Artificial Intelligence, 2015.Markdown
[Koriche et al. "Compiling Constraint Networks into Multivalued Decomposable Decision Graphs." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/koriche2015ijcai-compiling/)BibTeX
@inproceedings{koriche2015ijcai-compiling,
title = {{Compiling Constraint Networks into Multivalued Decomposable Decision Graphs}},
author = {Koriche, Frédéric and Lagniez, Jean-Marie and Marquis, Pierre and Thomas, Samuel},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {332-338},
url = {https://mlanthology.org/ijcai/2015/koriche2015ijcai-compiling/}
}