In this page we report some extra material related to recent papers on this topic.
The CUDA code for the constraint solver NVIDIOSO is available from
All the experiments posted in this page have been carried out on a CPU AMD Opteron 2.3 MHz, 132 GB memory, Linux 3.7.10-1.16-desktop x86 64.
The GPU is a GeForce GTX TITAN, 14 SMs, 875MHz, 6 GB global memory, CUDA 5.0 with compute capability 3.5.
Tests and benchmarks:
- Solving CSPs: we compare CPU and GPU implementations of the solver on randomly generated CSPs defined by inequalities constraints between pair of variables. These benchmarks test the performance of GPU-LNS on finding feasible starting points for LNS strategies. See here.
- Solving CSPs: Parallel Min Conflict Heuristic. We report some results comparing a Standard Min Conflict Heuristic (SMC) implementation vs s Large Neighborhood Min Conflict Heuristic (LNMC). LNMC evaluates multiple large neighborhoods (instead of one variable at a time as in SMC) and it chooses the one that has the lower number of conflict. See here.
- Evaluating LS strategies. We compare CPU and GPU considering 6 different LS strategies for exploring large neighborhoods: (1) Random Labeling (LN), (2) Random Permutation (RP), (3) Two-Exchange Permutation (2P), (4) Gibbs Sampling (GS), (5) Iterated Conditional Mode (ICM), and (6) Complete Exploration (CE). As benchmark we considered a modified version of the k-Coloring problem where the goal is to maximize the difference of colors between adjacent nodes. See here.
- Comparison with Standard CP. We evaluate the performance of the GPU-LNS solver against a state-of-the-art CP solver (JaCoP) on different COPs benchmarks. See here.
- Comparison with Standard LNS. We compare the GPU-LNS solver against a standard implementation of a LNS in OscaR on different COP benchmarks. See here.