A Parallelization of a Simulated Annealing Approach for 0-1 Multidimensional Knapsack Problem Using GPGPU

• Bianca De Almeida Dantas UFMS
• Edson Norberto Cáceres UFMS

Abstract

In the last decades, with the advances in multicore/manycore architectures, it became interesting to design algorithms which can take advantage of such architectures aiming the achievement of more efficient algorithms to solve difficult problems. A large number of real-world problems solved with the help of computer programs demand faster or better quality solutions. Some of these problems can be modeled as classical theoretical problems, such as the 0-1 multidimensional knapsack problem (0-1 MKP), known to belong to the NP-hard class of problems, for which we can not obtain an exact solution efficiently. This motivates the search for alternative strategies which can achieve good quality approximate solutions, like metaheuristics, and also different ways to enable their execution in reduced times, such as parallel algorithms which explore multicore/manycore architectures. In this work we describe a parallelization of a simulated annealing approachusing GPGPU to solve 0-1 MKP and compare our results to previous works in order to prove the viability of its use.

Keywords: Simulated annealing, Markov processes, Multicore processing, Graphics processing units, Algorithm design and analysis, 0-1 multidimensional knapsack problem, simulated annealing, GPGPU