A Constraint Store Based on Multivalued Decision Diagrams
A Constraint Store Based on Multivalued Decision Diagrams
复制标题
基于多值决策图的约束存储
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Peter Tiedemann
中科院分区：
文献类型：
--
作者：
H. Andersen;T. Hadzic;J. Hooker;Peter Tiedemann
典型的约束存储传输的信息量有限，因为它只由可变域组成。我们提出了一个更丰富的约束存储在一个有限宽度的多值决策图（MDD）的形式。当最大宽度为1时，它简化为传统的域存储，但允许对更大宽度的搜索树进行更大的修剪。MDD传播算法可以被开发来利用特定约束的结构，就像对域过滤算法所做的那样。我们提出了专门的传播算法alldiff和不等式约束。初步实验表明，MDD传播解决多个alldiff问题的数量级更快地比传统的域传播。它还显着减少了不等式问题的搜索树，但需要额外的研究来减少计算时间。
The typical constraint store transmits a limited amount of information because it consists only of variable domains. We propose a richer constraint store in the form of a limited-width multivalued decision diagram (MDD). It reduces to a traditional domain store when the maximum width is one but allows greater pruning of the search tree for larger widths. MDD propagation algorithms can be developed to exploit the structure of particular constraints, much as is done for domain filtering algorithms. We propose specialized propagation algorithms for alldiff and inequality constraints. Preliminary experiments show that MDD propagation solves multiple alldiff problems an order of magnitude more rapidly than traditional domain propagation. It also significantly reduces the search tree for inequality problems, but additional research is needed to reduce the computation time.