Skip to Main content Skip to Navigation
New interface
Conference papers

Defining and Evaluating Heuristics for the Compilation of Constraint Networks

Abstract : Several branching heuristics for compiling in a top-down fashion finite-domain constraint networks into multi-valued decision diagrams (MDD) or decomposable multi-valued decision graphs (MDDG) are empirically evaluated, using the cn2mddg compiler. This MDDG compiler has been enriched with various additional branching rules. These rules can be gathered into two families, the one consisting of heuristics for the satisfaction problem (which are suited to compiling networks into MDD representations) and the family of heuristics favoring decompositions (which are relevant when the MDDG language is targeted). Our empirical investigation on a large dataset shows the value of decomposability (targeting MDDG allows for compiling many more instances and leads to much smaller compiled representations). The well-known (Dom/Wdeg) heuristics appears as the best choice for compiling networks into MDD. When MDDG is the target, a new rule, based on a dynamic, yet parsimonious use of hypergraph partitioning for the decomposition purpose turns out to be the best option. As expected, the best heuristics for the satisfaction problem perform better than the best heuristics favoring decompositions when MDD is targeted, and the converse is the case when MDDG is targeted.
Document type :
Conference papers
Complete list of metadata
Contributor : Fabien DELORME Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2021 - 11:56:57 AM
Last modification on : Sunday, June 26, 2022 - 11:20:57 AM


  • HAL Id : hal-03300780, version 1



Jean-Marie Lagniez, Pierre Marquis, Anastasia Paparrizou. Defining and Evaluating Heuristics for the Compilation of Constraint Networks. 23rd International Conference on Principles and Practice of Constraint Programming (CP'17), 2017, Melbourne, Australia. pp.172-188. ⟨hal-03300780⟩



Record views