A CUDA based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization

Henrique Finglera, Edson N. Caceresa, Henrique Mongellia, Siang W. Songb
Universidade Federal do Mato Grosso do Sul, Campo Grande, MS, Brazil
Procedia Computer Science, Volume 29, Pages 84-94, 2014


   title={A CUDA based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization},

   author={Fingler, Henrique and C{‘a}ceres, Edson N and Mongelli, Henrique and Song, Siang W},

   journal={Procedia Computer Science},






Download Download (PDF)   View View   Source Source   



The Multidimensional Knapsack Problem (MKP) is a generalization of the basic Knapsack Problem, with two or more constraints. It is an important optimization problem with many real-life applications. To solve this NP-hard problem we use a metaheuristic algorithm based on ant colony optimization (ACO). Since several steps of the algorithm can be carried out concurrently, we propose a parallel implementation under the GPGPU paradigm (General Purpose Graphics Processing Units) using CUDA. To use the algorithm presented in this paper, it is necessary to balance the number of ants, number of rounds used, and whether local search is used or not, depending on the quality of the solution desired. In other words, there is a compromise between time and quality of solution. We obtained very promising experimental results and we compared our implementation with those in the literature. The results obtained show that ant colony optimization is a viable approach to solve MKP efficiently, even for large instances, with the parallel approach.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: