constraint Programming (CP) is an efficient technique for solving combinatorial (optimization) problems. In modern constraint solver, a CP Model is defined over reversible variables that take values in domains and pro...
详细信息
constraint Programming (CP) is an efficient technique for solving combinatorial (optimization) problems. In modern constraint solver, a CP Model is defined over reversible variables that take values in domains and propagators which filter the domains of the variables. constraintpropagation scheme schedules the propagators. A reasonable constraintpropagation algorithm can improve the efficiency of solving CP problems. In this paper, we propose two efficient parallelpropagation schemes based on multi-thread technique for table constraint. First, we give the formal definition of the parallel consistency and prove that the parallelpropagation scheme is equivalent to the classic serial propagation scheme. Then, we propose two parallelpropagation schemes: static submission and dynamic submission, which exploit work stealing thread pool and atomic operations to parallelize the classic propagation of table constraint. Finally, extensive experiments on various types of problems show that the two parallel schemes outperform their original serial version on a large number of instances. The results demonstrate the competitiveness of parallelpropagation algorithms on solving extensional constraints.
暂无评论