CP on GPU

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
https://github.com/FedericoCampe8/NVIDIOSO

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.