Propagating separable equalities in an MDD store

Tarik Hadzic, John N. Hooker, Peter Tiedemann

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

    Abstract

    We present a propagator that achieves MDD consistency for a separable equality over an MDD (multivalued decision diagram) store in pseudo-polynomial time. We integrate the propagator into a constraint solver based on an MDD store introduced in [1]. Our experiments show that the new propagator provides substantial computational advantage over propagation of two inequality constraints, and that the advantage increases when the maximum width of the MDD store increases.
    Original languageEnglish
    Book seriesLecture Notes in Computer Science
    Pages (from-to)318-322
    ISSN0302-9743
    DOIs
    Publication statusPublished - 2008
    EventCPAIOR 2008:The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - Paris, France
    Duration: 20 May 200823 May 2008

    Conference

    ConferenceCPAIOR 2008:The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
    Country/TerritoryFrance
    CityParis
    Period20/05/200823/05/2008

    Keywords

    • MDD consistency
    • Separable equality
    • Pseudo-polynomial time
    • Constraint solver
    • Computational advantage

    Cite this