Solving Graph Coloring Problem Using Parallel Discrete Particle Swarm Optimization on CUDA

Abstract

The graph coloring problem is one of the most well-known combinatorial optimization problems. It can be widely used in many fields. However, it is very difficult to find the global optimal solutions from exponential candidate solutions. In this paper, a parallel discrete particle swarm optimization algorithm based on compute unified device architecture (CUDA) is proposed to solve the graph coloring problem. With millions of CUDA-enabled GPUs, the algorithm can calculate the fitness function and update particles velocities and positions in parallel. In order to validate the effectiveness and efficiency of the proposed algorithm, some computational experiments are conducted on DIMACS benchmark graphs. The experiments results show that our algorithm provides competitive results and running time when compared with existing techniques on DIMACS instances.