Adaptive propagation algorithm based on bitwise operations

作者：Wang Hai Yan; Guo Jin Song^*; Ouyang Dan Tong; Zhang Yong Gang

来源：Journal of Jilin University (Engineering and Technology Edition), 2012, 42(5): 1219-1224.

• Adaptive constraints
• Bench-mark problems
• Bitwise operations
• Constraint propagation algorithms
• Constraint satisfaction problems
• Propagation algorithm

On the basis of the research of the constraint propagation algorithm, an adaptive constraint propagation algorithm, AC_MaxRPC_Bitwise, is proposed, which is based on bitwise operations. The proposed algorithm has several advantages in improving the efficiency of adaptive constraint propagation method. First, it introduces bitwise method to represent the data structure while looking for AC support and PC support. Second, it uses bitwise operation to speed up the searching process of AC support and PC witness. Experiments were conducted on a few typical benchmark problems. Results show that the improved algorithm AC_MaxRPC_Bitwise whelms AC and other constraint propagation algorithm in overall performance.

• 出版日期2012