Ant Colony System Based Solutions to the Quadratic Assignment Problem on GPGPU

The NP-hard Quadratic Assignment Problem (QAP) was proposed in 1957. Until this date, it remains one of the hardest problems to solve in any reasonable amount of time, even for small instances. Even using parallel computation and assuming small instances of the problem, some naive and deterministic algorithms require too much time to obtain the solution. In some cases an approximate approach would be satisfactory and heuristic and approximation algorithms have been proposed. In this paper we use heuristic techniques based on ant colony system to find approximate solutions for the QAP using GPGPUs (General-Purpose Computing on Graphics Processing Units). We review two methods to solve this problem: Hybrid Ant System (HAS-QAP algorithm) and the cunning Ant System (cASQAP algorithm). We parallelize both algorithms to run on a GPU, using CUDA. The parallelized HAS version (called CUDAHAS) outperforms the parallel cAS algorithm and we present performance results of this parallel algorithm with respect to its sequential counterpart. We used four well-known input instances (named els19, nug30, sko72 and wil100), of sizes ranging from 19 to 100, whose best solutions are known. Our results show the power of the GPU algorithm CUDA-HAS in the case when the required error margin is small (0.1% error), where our CUDA-HAS algorithm was able to present a speedup of 103 with respect to the sequential execution time by the CPU alone, for the instance nug30. The HAS-GPU algorithm is indicated when we wish to solve the QAP for large sizes (up to 100) with a solution that is close to the optimum.