Compiling Constraint Networks into Multivalued Decomposable Decision Graphs

Koriche, Frédéric; Lagniez, Jean-Marie; Marquis, Pierre; Thomas, Samuel

Compiling Constraint Networks into Multivalued Decomposable Decision Graphs

Frédéric Koriche, Jean-Marie Lagniez, Pierre Marquis, Samuel Thomas

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 332-337.

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).

Frédéric Koriche, Jean-Marie Lagniez, Pierre Marquis, and Samuel Thomas. 2015. Compiling Constraint Networks into Multivalued Decomposable Decision Graphs. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 332–337. https://ijcai.org/proceedings/2015/53

@inproceedings{ijcai2015p53,
  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 = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {332--337},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/53},
}

TY  - CPAPER
TI  - Compiling Constraint Networks into Multivalued Decomposable Decision Graphs
AU  - Koriche, Frédéric
AU  - Lagniez, Jean-Marie
AU  - Marquis, Pierre
AU  - Thomas, Samuel
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 332
EP  - 337
UR  - https://ijcai.org/proceedings/2015/53
ER  -