|
|
|
| Improved RDS Symbol Algebraic Decision Diagram Algorithm for Weighted Constraint Satisfaction Problem |
| XU Zhou-Bo, YANG Xin-Liang, GU Tian-Long, Ning Li-Hua |
| Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004 |
|
|
|
|
Abstract 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.
|
|
Received: 31 December 2014
|
|
|
|
|
|
|
|
|
2015, Vol. 28 
