Solving the Multidimensional Knapsack Problem using a CUDA accelerated PSO

The Multidimensional Knapsack Problem (MKP) represents an important model having numerous applications in combinatorial optimisation, decision-making and scheduling processes, cryptography, etc. Although the MKP is easy to define and implement, the time complexity of finding a good solution grows exponentially with the problem size. Therefore, novel software techniques and hardware platforms are being developed and employed to reduce the computation time. This paper addresses the possibility of solving the MKP using a GPU accelerated Particle Swarm Optimisation (PSO). The goal is to evaluate the attainable performance benefit when using a highly optimised GPU code instead of an efficient multi-core CPU implementation, while preserving the quality of the search process. The paper shows that a single Nvidia GTX 580 graphics card can outperform a quad-core CPU by a factor of 3.5 to 9.6, depending on the problem size. As both implementations are memory bound, these speed-ups directly correspond to the memory bandwidth ratio between the investigated GPU and CPU.