An experimental evaluation of a parallel simulated annealing approach for the 0-1 multidimensional knapsack problem

The recent progresses in the development and improvement of multicore/manycore architectures instigate the design of algorithms capable of exploring the functionalities provided by these architectures to solve more efficiently hard problems. The NP-hard class of problems contains several problems which demand for efficient alternative solutions, since there is a wide range or real-world problems which can be modeled as one of them and it is unknown if they can be exactly solved in feasible time. The 0-1 multidimensional knapsack problem (0-1 MKP) is one of the most emblematic NP-hard problems and this work focuses on the proposal of a parallel simulated annealing algorithm using GPGPU. The results achieved by the parallel SA were compared to other reference works and showed that GPGPU is effective on the task of obtaining better quality solutions in reduced execution time when compared to sequential programs. Our proposed approach can be adapted to other parallel platforms.