Parallelization of constraint programming using embarrassingly parallel search

Constraint programming solvers have a serial architecture, and do not take advantage of the parallel computing power available nowadays in our multi-core computers and in the cloud. Multiple solutions to remedy at this situation have emerged, such as Work-Stealing or Multi-threaded Portfolio Search, which allow to run multiple solvers and make them communicate in order to find solutions of the initial problem. However, these techniques scale badly with a high number of workers. Embarrassingly Parallel Search is a recent method that aims at parallelizing solving of constraint satisfaction problems, by dividing them in numerous subproblems, and sharing them between multiple solvers. The high number of subproblems ensures proper balancing between the multiple workers. Previous works have shown nearly linear speedups and superiority of EPS over other methods on some problems. This master's thesis proposes a new implementation of EPS over the OscaR-CP solver, with an innovative architecture based on a symbolic layer, called OscaR-Modeling, that is inspired by Objective-CP, a state-of-the-art modeling language. An analysis of the influence of the decomposition method over the speedup is made, and a new decomposition, called Cartesian Product Iterative Refinement, is proposed. EPS is originally made for solving constraint satisfaction problems; this master's thesis introduces an adaptation for constraint optimization problems. A study of various methods to share the objective function bound is conducted. Finally, an overview of the performances of EPS on OscaR-Modeling is given, and shows linear and super-linear speedups, even on more than one thousand threads.