---
title: "Compiling Constraint Networks into Multivalued Decomposable Decision Graphs"
authors:
  - "Frédéric Koriche"
  - "Jean-Marie Lagniez"
  - "Pierre Marquis"
  - "Samuel Thomas"
doi: ""
url: "https://ijcai.org/proceedings/2015/53"
pdf: "https://ijcai.org/proceedings/2015/0053.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "332-337"
track: "Main Track"
keywords:
---

# Compiling Constraint Networks into Multivalued Decomposable Decision Graphs

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

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, 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).