ITU

Approximate Compilation of Constraints into Multivalued Decision Diagrams

Research output: Journal Article or Conference Article in JournalConference articleResearchpeer-review

View graph of relations

We present an incremental refinement algorithm for approximate compilation of constraint satisfaction models into multivalued decision diagrams (MDDs). The algorithm uses a vertex splitting operation that relies on the detection of equivalent paths in the MDD. Although the algorithm is quite general, it can be adapted to exploit constraint structure by specializing the equivalence tests for partial assignments to particular constraints. We show how to modify the algorithm in a principled way to obtain an approximate MDD when the exact MDD is too large for practical purposes. This is done by replacing the equivalence test with a constraint-specific measure of distance. We demonstrate the value of the approach for approximate and exact MDD compilation and evaluate its benefits in one of the main MDD application domains, interactive configuration.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)448-462
ISSN0302-9743
DOIs
Publication statusPublished - 2008
Event14. CP 2008: Sydney, NSW, Australia: Principles and Practice of Constraint Programming, 14th International Conference, CP 2008 - Sydney, Australia
Duration: 14 Sep 200818 Sep 2008
Conference number: 14

Conference

Conference14. CP 2008: Sydney, NSW, Australia: Principles and Practice of Constraint Programming, 14th International Conference, CP 2008
Number14
CountryAustralia
CitySydney
Period14/09/200818/09/2008

ID: 955628