Maintaining persistent MDD for arc consistency

Maintenir des MDD persistants pour établir la consistance d’arc

Julien Vion (1) , Sylvain Piechowiak (1)

1 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

In this paper, we present MDDF, a new algorithm for revising constraints defined using multi-valued decision diagrams (MDD). MDDF copies modified parts of the MDD "on the fly" during the search of a solution, which yields a better incrementality than the previous MDDC algorithm by Cheng et Yap (2010), although coarse-grained propagation queues are still sufficient. MDDF can also be used to compress constraints defined as tables of allowed tuples. MDDF has then comparable performances to the STR2 algorithm by Ullmann (2007) and Lecoutre (2011) on loose, unstructured constraints

Mots clés: "CSP"; "MDD"; "Propagation"; "Tables"

Domaines: Informatique [cs]

Julien Vion, Sylvain Piechowiak. Maintenir des MDD persistants pour établir la consistance d’arc. Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle, 2014, 28 (5), pp.547-569. ⟨10.3166/RIA.28.547-569⟩. ⟨hal-03663860⟩