加权约束满足问题的改进RDS符号代数决策图求解算法

Improved RDS Symbol Algebraic Decision Diagram Algorithm for Weighted Constraint Satisfaction Problem

加权约束满足问题(WCSP)是一类约束最优化问题.文中基于RDS思想,从减少RDS分解的子问题个数及提高各个子问题的求解效率入手,提出WCSP的改进RDS符号代数决策图(ADD)求解算法.通过改进最多约束变量的变量选择法,引入RDS变量引导原问题的子问题分解,进而减少RDS中分解的子问题个数.利用变量的后向度,进一步改进子问题的分解方法.为提高各个子问题的求解效率,利用桶消元算法并结合ADD操作消去子问题中的非RDS变量,进而减少子问题中的变量个数,提高深度优先分支界定法的下界.在大量随机生成的测试用例上的实验证明文中算法的优越性.

Weighted constraint satisfaction problem （WCSP） is a kind of constraint optimization problem. Based on Russian doll search （RDS） algorithm, an improved RDS symbolic algebraic decision diagram （ADD） algorithm for WCSP is proposed to reduce the number of sub-problems and improve the efficiency of solving sub-problems of original RDS algorithm. Through improving the most constraining variable （MCV） method of variable selection, a concept of RDS variable is introduced and conducted for nested decomposition of the original problem. Then, the number of sub-problems is decreased. Furthermore, the nested decomposition method is improved by variable back-degree. To improve the efficiency of solving sub-problems, the bucket elimination algorithm combined with ADD operation is exploited to eliminate the non-RDS variables. And thus the number of variables in the sub-problem is decreased and the lower bound is improved. Experiments on a large number of random generated testing cases demonstrate the superiority of the proposed algorithm.