ITU

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

Hadzic, T, Hooker, JN, O’Sullivan, B & Tiedemann, P 2008, 'Approximate Compilation of Constraints into Multivalued Decision Diagrams', Lecture Notes in Computer Science, pp. 448-462. https://doi.org/10.1007/978-3-540-85958-1_30

APA

Hadzic, T., Hooker, J. N., O’Sullivan, B., & Tiedemann, P. (2008). Approximate Compilation of Constraints into Multivalued Decision Diagrams. Lecture Notes in Computer Science, 448-462. https://doi.org/10.1007/978-3-540-85958-1_30

Vancouver

Hadzic T, Hooker JN, O’Sullivan B, Tiedemann P. Approximate Compilation of Constraints into Multivalued Decision Diagrams. Lecture Notes in Computer Science. 2008;448-462. https://doi.org/10.1007/978-3-540-85958-1_30

Author

Hadzic, Tarik ; Hooker, John N. ; O’Sullivan, Barry ; Tiedemann, Peter. / Approximate Compilation of Constraints into Multivalued Decision Diagrams. In: Lecture Notes in Computer Science. 2008 ; pp. 448-462.

Bibtex

@inproceedings{8f4288a0f6a211dd9b71000ea68e967b,
title = "Approximate Compilation of Constraints into Multivalued Decision Diagrams",
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. ",
author = "Tarik Hadzic and Hooker, {John N.} and Barry O{\textquoteright}Sullivan and Peter Tiedemann",
note = "Volumne: 5202; null ; Conference date: 14-09-2008 Through 18-09-2008",
year = "2008",
doi = "10.1007/978-3-540-85958-1_30",
language = "English",
pages = "448--462",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer",

}

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