Approximate Compilation of Constraints into Multivalued Decision Diagrams
Approximate Compilation of Constraints into Multivalued Decision Diagrams
复制标题
将约束近似编译为多值决策图
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Peter Tiedemann
中科院分区：
文献类型：
--
作者：
T. Hadzic;J. Hooker;B. O’Sullivan;Peter Tiedemann
提出了一种将约束满足模型近似编译成多值决策图（mdd）的增量改进算法。该算法使用顶点分割操作，该操作依赖于MDD中等效路径的检测。虽然该算法很通用，但它可以通过将部分赋值的等价性测试专门化到特定的约束条件中来利用约束结构。当精确的MDD对于实际目的来说太大时，我们将展示如何以一种有原则的方式修改算法以获得近似的MDD。这是通过用特定于约束的距离度量代替等效检验来实现的。我们演示了该方法对近似和精确MDD编译的价值，并评估了它在一个主要的MDD应用领域（交互式配置）中的好处。
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.