An effective Parallel Multistart Tabu Search for Quadratic Assignment Problem on CUDA platform

NVidia’s powerful GPU hardware and CUDA platform enables the design of very fast parallel algorithms. Relatively little research has been done so far on GPU implementations of algorithms for computationally demanding discrete optimisation problems. In this paper, the well-known NPNP-hard Quadratic Assignment Problem (QAP) is considered. Detailed analysis of parallelisation possibilities, memory organisation and access patterns, enables the implementation of fast and effective heuristics for QAP on the GPU — the Parallel Multistart Tabu Search (PMTS). Computational experiments show that PMTS is capable of providing good quality (often optimal or the best known) solutions in a short time, and even better quality solutions in longer runs. PMTS runs up to 420×420× faster than a single-core counterpart, or 70×70× faster than a parallel CPU implementation on a high-end six-core CPU.

► Parallel Multistart Tabu Search for QAP, implemented on GPU (CUDA) is proposed.
► Analysis of parallelisation possibilities and memory access patterns is presented.
► PMTS runs up to 420×420× faster than a single-core CPU or 70×70× faster than a 6-core CPU.
► PMTS finds good quality (often optimal or the best known) solutions in a short time.
► The quality of solutions improves even further, when PMTS is run for a longer time.