Paper Info
Title
Sequential And Parallel Implementation Of Grasp For The 0-1 Multidimensional Knapsack Problem
Abstract
The knapsack problem is a widely known problem in combinatorial optimization and has been object of many researches in the last decades. The problem has a great number of variants and obtaining an exact solution to any of these is not easily accomplished, which motivates the search for alternative techniques to solve the problem. Among these alternatives, metaheuristics seem to be suitable on the search for approximate solutions for the problem. In this work we propose a sequential and a parallel implementation for the multidimensional knapsack problem using GRASP metaheuristic. The obtained results show that GRASP can lead to good quality results, even optimal in some instances, and that CUDA may be used to expand the neighborhood search and as a result may lead to improved quality results.
Year
DOI
Venue
2015
10.1016/j.procs.2015.05.411
INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE, ICCS 2015 COMPUTATIONAL SCIENCE AT THE GATES OF NATURE
Keywords
Field
DocType
GRASP, 0-1 multidimensional knapsack problem, CUDA
Mathematical optimization,GRASP,Computer science,Change-making problem,Generalized assignment problem,Continuous knapsack problem,Combinatorial optimization,Artificial intelligence,Cutting stock problem,Knapsack problem,Machine learning,Metaheuristic
Conference
Volume
ISSN
Citations 
51
1877-0509
1
PageRank 
References 
Authors
0.35
4
2
Name
Order
Citations
PageRank
Bianca de Almeida Dantas141.82
Edson Norberto Cáceres2297.30