Experimenting with Constraint Programming on GPU

Abstract

The focus of my PhD thesis is on exploring parallel approaches to efficiently solve problems modeled by constraints and presenting a new proposal. Current solvers are very advanced; they are carefully designed to effectively manage the high-level problems' description and include refined strategies to avoid useless work. Despite this, finding a solution can take an unacceptable amount of time. Parallelization can mitigate this problem when the instance of the problem modeled is large, as it happens in real world problems. It is done by propagating constraints in parallel and concurrently exploring different parts of the search space. I am developing on a constraint solver that exploits the many cores available on Graphics Processing Units (GPU) to speed up the search.