Approximate Compilation of Constraints into Multivalued Decision Diagrams
Research output: Journal Article or Conference Article in Journal › Conference article › Research › peer-review
Standard
Approximate Compilation of Constraints into Multivalued Decision Diagrams. / Hadzic, Tarik; Hooker, John N.; O’Sullivan, Barry; Tiedemann, Peter.
In: Lecture Notes in Computer Science, 2008, p. 448-462.Research output: Journal Article or Conference Article in Journal › Conference article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Approximate Compilation of Constraints into Multivalued Decision Diagrams
AU - Hadzic, Tarik
AU - Hooker, John N.
AU - O’Sullivan, Barry
AU - Tiedemann, Peter
N1 - Conference code: 14
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-540-85958-1_30
DO - 10.1007/978-3-540-85958-1_30
M3 - Conference article
SP - 448
EP - 462
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
SN - 0302-9743
Y2 - 14 September 2008 through 18 September 2008
ER -
ID: 955628