The cn2mddg compiler

Compiling constraint natworks (CN) into multivalued decomposable decision graphs (MDDG)

cn2mddg is a compiler associating with a finite-domain constraint network represented in the XCSP 2.1 format an equivalent representation from the language MDDG of multivalued decomposable decision graphs. MDDG is precisely the extension to non-Boolean domains of the language of Decision-DNNF: it is based on decomposable AND-nodes and (multivalued) decision nodes. Similarly to Decision-DNNF, the MDDG language offers a number of tractable queries, including (possibly weighted) solution finding and counting, solution enumeration (solutions can be enumerated with polynomial delay), and optimization w.r.t. a linear objective function.

Ressources for the cn2mddg compiler (V 1.0)

New release (V 2.0)

For more details, see the papers:

F.Koriche, J.-M. Lagniez, P. Marquis and S. Thomas. "Compiling Constraint Networks into Multivalued Decomposable Decision Graphs". Proceedings of IJCAI'15, pages 332-338. (pdf)
J.-M. Lagniez, P. Marquis and A. Paparrizou. "Defining and Evaluating Heuristics for the Compilation of Constraint Networks". Proceedings of CP'17, pages 172-188. (pdf)

How to use cn2mddg

cn2mddg is the run-time code of our compiler on a linux64 architecture.

In order to compile the instance given in file name.xcsp, use:
$ cn2mddg -cn2mddg < name.xcsp

[Similarly, for compiling name.xml, use:
$ cn2mddg -cn2mddg < name.xml

The standard output reports the size of the compiled MDDG representation (in number of arcs), the compilation time, the number of AND nodes in the compiled MDDG representation, the number of OR nodes in the compiled MDDG representation, and the number of solutions.

cn2mddg can also be used to translate the input constraint network into a CNF formula such that the models of this output formula are in one-to-one correspondence with the solutions of the input network.

In order to translate name.xcsp into a CNF representation, use:
$ cn2mddg -toCNF -type name.cnf < name.xcsp

This command line creates the file name.cnf containing a CNF formula in DIMACS format which has the same number of solutions as name.xcsp.

More help can be obtained using cn2mddg -h.

picturesMDDG.zip contains some plots; all those plots are scattered plots, except timeCactus.pdf which is a cactus plot, indicating for the four approaches considered in the paper the number of instances (on the x-axis) which can be compiled within a given amount of time (on the y-axis).

The files size-cn2mddg-vs-dsharp.pdf and time-cn2mddg-vs-dsharp.pdf contain the scattered plots given in the paper.

The file size-dwdeg-vs-centrality.pdf (resp. time-dwdeg-vs-centrality.pdf) contains a scattered plot enabling to compare the sizes (resp. the compilation times) for cn2mddg equipped with the betweenness centrality heuristic (as discussed in the paper) with cn2mddg equipped with the usual dom/wdeg heuristic.

The remaining files contain scattered plots enabling to compare the sizes (or the compilation times) required by cn2mddg equipped with either the centrality heuristics or the dom/wdeg heuristic, with Dsharp for a specified CN2CNF encoding. For instance, size-dwdeg-vs-dsharpDirect.pdf contains a scattered plot on which are reported the sizes of the MDDG compiled representations obtained using cn2mddg equipped with the dom/wdeg heuristic, with the sizes of the Decision-DNNF representations obtained using Dsharp when the direct encoding is used for the domains (i.e., one uses one propositional variable for each pair (variable, value)), and a mixed encoding is used for the constraints.