Symbolic ADD Algorithms for Weighted Constraint Satisfaction Problem
XU Zhou-Bo1,2, GU Tian-Long2 , CHANG Liang2
1.School of Electronic Engineering, Xidian University, Xian 710071 2.School of Computer Science and Engineering, Guilin University of Electronic Technology, Guilin 541004
Abstract The weighted constraint satisfaction problem (WCSP) is a kind of soft constraint satisfaction problems with many practical applications. An algebraic decision diagram (ADD) based scheme is proposed to solve WCSP efficiently. Firstly, the soft constraint network is represented as ADDs so that the WCSP can be formulated symbolically and manipulated implicitly. Secondly, the symbolic ADD algorithm is presented, where the branch and bound algorithm is integrated with bucket elimination algorithm symbolically. And the static variable orderings and the node consistency during search are used. To improve the lower bound of the symbolic ADD algorithm, the counting technique of directional arc consistency is adopted, and thus the symbolic ADD algorithm is improved. Finally, experiments on random problems are implemented, and the results show that the proposed algorithms outperform the depth-first branch and bound algorithms enhanced with a look-ahead process and a preprocessing step of either existential directional arc consistency or the node consistency.
[1] He Renjie, Tan Yuejin. Improved Depth-First Search Algorithm for Valued Constraint Satisfaction Problem. Journal of Systems Engineering, 2004, 19(5):512-516 (in Chinese) (贺仁杰,谭跃进.加权约束满足问题的改进深度优先搜索算法. 系统工程学报, 2004, 19(5): 512-516) [2] Larrosa J, Schiex T. Solving Weighted CSP by Maintaining Arc-Consistency. Artificial Intelligence, 2004, 159(1/2): 1-26 [3] Dechter R. Bucket Elimination: A Unifying Framework for Reasoning. Artificial Intelligence, 1999, 113(1/2): 41-85 [4] Larrosa J, Schiex T. In the Quest of the Best Form of Local Consistency for Weighted CSP // Proc of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 239-244 [5] de Givry S, Zytnicki M, Heras F, et al. Existential Arc Consistency: Getting Closer to Full Arc Consistency in Weighted CSP // Proc of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, Scotland, 2005: 84-89 [6] Gu Tianlong, Xu Zhoubo. Ordered Binary Decision Diagram and Its Application. Beijing, China: Science Press, 2009 (in Chinese) (古天龙,徐周波.有序二叉决策图及应用.北京:科学出版社, 2009) [7] Bryant R E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams. ACM Computing Surverys, 1992, 24(3): 293-318 [8] Bachar R I, Frohm E A, Gaona C M, et al, Algebraic Decision Diagrams and Their Applications. Formal Methods in Systems Design, 1997, 10(2/3): 171-206 [9] Hachtel G D, Somenzi F. A Symbolic Algorithm for Maximum Flow in 0-1 Networks. Formal Methods in System Design, 1997, 10(2/3): 207-219 [10] Xu Zhoubo, Gu Tianlong, Zhao Lingzhong. A Novel Symbolic ADD Algorithm for Maximum Flow in Networks. Journal on Communications, 2005, 26(2):1-8 (in Chinese) (徐周波,古天龙,赵岭忠.网络最大流问题的一种新的符号ADD求解算法.通信学报, 2005, 26(2): 1-8) [11] Chatalic P, Simon L. Multi-Resolution on Compressed Sets of Clauses // Proc of the 12th International Conference on Tools with Artificial Intelligence. Vancouver, Canada, 2000: 2-10 [12] Pan Guoqiang, Vardi M Y. Symbolic Techniques in Satisfiability Solving. Journal of Automated Reasoning, 2005, 35(1/3): 25-50 [13] Larrosa J, Meseguer P. Exploiting the Use of DAC in Max-CSP // Proc of the 2nd International Conference on Principle and Practice of Constraint Programming. Cambridge, USA, 1996: 308-322 [14] Wallace R J. Directed Arc Consistency Preprocessing // Proc of the Workshop on Constraint Processing. Berlin, Germany: Springer-Verlag, 1995: 121-137
2011, Vol. 24 
