Approximate Compilation of Constraints into Multivalued Decision Diagrams

Tarik Hadzic, John N. Hooker, Barry O’Sullivan, Peter Tiedemann

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

    Abstract

    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 Sept 200818 Sept 2008
    Conference number: 14

    Conference

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

    Cite this