A Novel Multi-Thread Parallel Constraint Propagation Scheme

Abstract

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. Constraint propagation scheme schedules the propagators. A reasonable constraint propagation algorithm can improve the efficiency of solving CP problems. In this paper, we propose two efficient parallel propagation schemes based on multi-thread technique for table constraint. First, we give the formal definition of the parallel consistency and prove that the parallel propagation scheme is equivalent to the classic serial propagation scheme. Then, we propose two parallel propagation 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 parallel propagation algorithms on solving extensional constraints.

Keywords

• Constraint programming
• constraint satisfaction problem
• parallel constraint propagation
• parallel generalized arc consistency
• simple tabular reduction