posted on 1983-01-01, 00:00authored byTarik Hadzic, John N. Hooker, Barry O'Sullivan, Peter Tiedemann
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.