Compile! Project - CRIL-CNRS & Univ. Artois

Compiling constraint networks (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)

• the runtime code of our compiler cn2mddg
• the benchmarks themselves (set of benchmarks). The folder contains all the benchmarks used in our experiments. Each file is suffixed by .xcsp or by .xml, but the distinction between the two suffixes is not relevant.
• a table synthesizing the empirical results (full table)

New release (V 2.0)

• a new release of the compiler including many additional heuristics for branching will be available soon
• some scatter plots synthesizing the empirical results are available here

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.

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.

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.

• "type" specifies the encoding method used; its possible values are:
• "conflict": Direct Conflict Encoding
• "support": Direct Support Encoding
• "log": Log Conflict Encoding
• "logsup": Log Support Encoding
• "mixed": Mixed Direct Encoding

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.