Solving Combinatorial Problems with Parallel Cooperative Solvers

Abstract. To exploit multi-core computing power, this paper presents parallel cooperative solvers for solving constraint satisfaction and optimization problems. Each solver owns the entire problem and exchanges partial solutions with other solvers. We applied Solution-Guided Multi-Point Constructive Search to the quasigroup-with-holes completion problem and Tabu Search to the quadratic assignment problem. Experimental results demonstrate that adding more solvers helps to improve the performance for both problems. We also introduce communication graphs and import policies to change solver cooperation. A combination of communication graph and import policy significantly impacts the performance, where the benefit from cooperation differs on the two problems: cooperation improves performance on the quasigroup-with-holes but not on the quadratic assignment problem.