A Load Balancing Procedure for Parallel Constraint Programming
Simon Boivin, Bernard Gendron, Gilles Pesant · PolyPublie (École Polytechnique de Montréal) · 2008
In this paper, we design a parallel Constraint Programming (CP) method to solve Constraint Satisfaction Problems (CSP). We use some attributes induced by the CP model of a CSP to improve the load balancing procedure embedded in the parallel tree- based search algorithm. Load balancing is improved by using specialized branching heuristics and workload estimators based on the CP model. More precisely, solution counting is used as an approximation of the computational size of the tasks in the parallel CP solver. This approximation of the workload of a task improves the work decomposition or work splitting procedure as well as the distribution of the tasks in the parallel algorithm. Experimental results indicate that this information speeds up the parallel exploration of the search tree.