From MDD to BDD and Arc consistency

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 a new conversion of multivalued decision diagrams (MDD) to binary decision diagrams (BDD) which can be used to improve MDD-based fil- tering algorithms such as MDDC or MDD-4R. We also propose BDDF, an algorithm that copies modified parts of the BDD “on the fly” during the search of a solution, and yields a better incrementality than a pure MDDC-like approach. MDDC is not very efficient when used to represent poorly structured positive table constraints. Our new representation combined with BDDF retains the properties of the MDD representation and has comparable performances to the STR2 algorithm by Ullmann (2007) and Lecoutre (Constraints, 16.4, 341–371 2011).

Domaines: Informatique [cs]

Julien Vion, Sylvain Piechowiak. From MDD to BDD and Arc consistency. Constraints, 2018, 23 (4), pp.451-480. ⟨10.1007/s10601-018-9286-5⟩. ⟨hal-03400583⟩