Paper Info
Title
A Parallelization of a Simulated Annealing Approach for 0-1 Multidimensional Knapsack Problem Using GPGPU
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.
Year
DOI
Venue
2016
10.1109/SBAC-PAD.2016.25
2016 28th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)
Keywords
Field
DocType
0-1 multidimensional knapsack problem,simulated annealing,GPGPU
Simulated annealing,Parallel algorithm,Computer science,Parallel computing,Continuous knapsack problem,Theoretical computer science,General-purpose computing on graphics processing units,Knapsack problem,Multi-core processor,Metaheuristic
Conference
ISSN
ISBN
Citations 
1550-6533
978-1-5090-6109-9
0
PageRank 
References 
Authors
0.34
7
2
Name
Order
Citations
PageRank
Bianca de Almeida Dantas141.82
Edson Norberto Cáceres2297.30