Skip to main content
Article
Approximate Compilation of Constraints into Multivalued Decision Diagrams
P. J. Stuckey, ed., Principles and Practice of Constraint Programming (CP 2008)
  • Tarik Hadzic, Cork Constraint Computation Centre
  • John N. Hooker, Carnegie Mellon University
  • Barry O'Sullivan, Cork Constraint Computation Centre
  • Peter Tiedemann, IT University of Copenhagen
Date of Original Version
1-1-2008
Type
Book Chapter
Abstract or Description
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 detection of equivalent paths in the MDD. Although the algorithm is quite general, it can be adapted to exploit constraint structure by specializing the path equivalence test 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.
DOI
10.1007/978-3-540-85958-1_30
Citation Information
Tarik Hadzic, John N. Hooker, Barry O'Sullivan and Peter Tiedemann. "Approximate Compilation of Constraints into Multivalued Decision Diagrams" P. J. Stuckey, ed., Principles and Practice of Constraint Programming (CP 2008) Vol. LNCS 5202 (2008) p. 448 - 462
Available at: http://works.bepress.com/jnhooker/68/