A GPU-based DP algorithm for solving multiple instances of the knapsack problem
Resumo
The knapsack problem is a classic and fundamental optimisation problem that serves as a subproblem in various optimisation algorithms. Thus, it is of great importance that we manage to solve several instances of the knapsack problem in a fast and efficient way. In this work we present a parallel algorithm, based on dynamic programming, that can take advantage of parallelism as more knapsacks need to be solved. The algorithm makes use of fine-grained data parallelism and is easily mapped to GPU accelerators. Extensive experiments with diverse datasets demonstrate the superiority of the proposed algorithm, achieving relevant speedups compared to a serial algorithm.
Palavras-chave:
Multidimensional Knapsack, Graphics Processing Unit, MKP, GPU, Dynamic Programming
Referências
Bansal, J. C. and Deep, K. (2012). A Modified Binary Particle Swarm Optimization for Knapsack Problems. Appl. Math. Comput., 218:11042–11061.
Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1 edition.
Berger, K.-E. and Galea, F. (2013). An efficient parallelization strategy for dynamic programming on gpu. In 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, pages 1797–1806. IEEE.
Biswas, G. and Mukherjee, N. (2022). An Efficient Reduced-Memory GPU-based Dynamic Programming Strategy for Bounded Knapsack Problems. In 2022 Seventh In ternational Conference on Parallel, Distributed and Grid Computing (PDGC), pages 18–23. IEEE.
de Almeida Dantas, B. and Cáceres, E. N. (2014). A parallel implementation to the multidimensional knapsack problem using augmented neural networks. In Proceedings of the 2014 Latin American Computing Conference, CLEI 2014, pages 1–9.
de Almeida Dantas, B. and Cáceres, E. N. (2015). Sequential and Parallel Implementation of GRASP for the 0-1 Multidimensional Knapsack Problem. In Procedia Computer Science, pages 2739–2743.
de Almeida Dantas, B. and Cáceres, E. N. (2016). A Parallelization of a Simulated Annealing Approach for 0-1 Multidimensional Knapsack Problem Using GPGPU. In Symposium on Computer Architecture and High Performance Computing, pages 134–140.
de Almeida Dantas, B. and Cáceres, E. N. (2018). An experimental evaluation of a parallel simulated annealing approach for the 0–1 multidimensional knapsack problem. Journal of Parallel and Distributed Computing, 120:211–221.
Fingler, H., Cáceres, E., Mongelli, H., and Song, S. (2014). A CUDA based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization. Procedia Computer Science, 29:84–94.
Gavish, B. and Pirkul, H. (1982). Allocation of Databases and Processors in a Distributed Computing System. In Akoka, J., editor, Management of Distributed Data Processing, volume 31, pages 215–231. North-Holland.
Gilmore, P. C. and Gomory, R. E. (1966). The Theory and Computation of Knapsack Functions. Operations Research, 14(6):1045–1074.
Kellerer, H., Pferschy, U., and Pisinger, D. (2004). Knapsack Problems. Springer.
Kirk, D. B. and Hwu, W.-M. W. (2016). Programming massively parallel processors. Morgan Kaufmann, Oxford, England, 3 edition.
Lorie, J. H. and Savage, L. J. (1955). Three problems in capital rationing. Journal of Business, 28(4):229–239.
Mesyagutov, M., Scheithauer, G., and Belov, G. (2012). LP bounds in various constraint programming approaches for orthogonal packing. Computers & Operations Research, 39(10):2425–2438.
Nvidia (2023). CUDA C Programming Guide — docs.nvidia.com. [link]. [Accessed 09-09-2023].
Pfeffer, A. (2007). Sampling with memoization. In Proc. of the 22nd National Conference on Artificial Intelligence Volume 2, AAAI’07, pages 1263–1270. AAAI Press.
Shih, W. (1979). A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem. Journal of the Operational Research Society, 30(4):369–378.
Zan, D. and Jaros, J. (2014). Solving the Multidimensional Knapsack Problem using a CUDA accelerated PSO. In IEEE Congress on Evolutionary Computation, CEC 2014, pages 2933–2939.
Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1 edition.
Berger, K.-E. and Galea, F. (2013). An efficient parallelization strategy for dynamic programming on gpu. In 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, pages 1797–1806. IEEE.
Biswas, G. and Mukherjee, N. (2022). An Efficient Reduced-Memory GPU-based Dynamic Programming Strategy for Bounded Knapsack Problems. In 2022 Seventh In ternational Conference on Parallel, Distributed and Grid Computing (PDGC), pages 18–23. IEEE.
de Almeida Dantas, B. and Cáceres, E. N. (2014). A parallel implementation to the multidimensional knapsack problem using augmented neural networks. In Proceedings of the 2014 Latin American Computing Conference, CLEI 2014, pages 1–9.
de Almeida Dantas, B. and Cáceres, E. N. (2015). Sequential and Parallel Implementation of GRASP for the 0-1 Multidimensional Knapsack Problem. In Procedia Computer Science, pages 2739–2743.
de Almeida Dantas, B. and Cáceres, E. N. (2016). A Parallelization of a Simulated Annealing Approach for 0-1 Multidimensional Knapsack Problem Using GPGPU. In Symposium on Computer Architecture and High Performance Computing, pages 134–140.
de Almeida Dantas, B. and Cáceres, E. N. (2018). An experimental evaluation of a parallel simulated annealing approach for the 0–1 multidimensional knapsack problem. Journal of Parallel and Distributed Computing, 120:211–221.
Fingler, H., Cáceres, E., Mongelli, H., and Song, S. (2014). A CUDA based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization. Procedia Computer Science, 29:84–94.
Gavish, B. and Pirkul, H. (1982). Allocation of Databases and Processors in a Distributed Computing System. In Akoka, J., editor, Management of Distributed Data Processing, volume 31, pages 215–231. North-Holland.
Gilmore, P. C. and Gomory, R. E. (1966). The Theory and Computation of Knapsack Functions. Operations Research, 14(6):1045–1074.
Kellerer, H., Pferschy, U., and Pisinger, D. (2004). Knapsack Problems. Springer.
Kirk, D. B. and Hwu, W.-M. W. (2016). Programming massively parallel processors. Morgan Kaufmann, Oxford, England, 3 edition.
Lorie, J. H. and Savage, L. J. (1955). Three problems in capital rationing. Journal of Business, 28(4):229–239.
Mesyagutov, M., Scheithauer, G., and Belov, G. (2012). LP bounds in various constraint programming approaches for orthogonal packing. Computers & Operations Research, 39(10):2425–2438.
Nvidia (2023). CUDA C Programming Guide — docs.nvidia.com. [link]. [Accessed 09-09-2023].
Pfeffer, A. (2007). Sampling with memoization. In Proc. of the 22nd National Conference on Artificial Intelligence Volume 2, AAAI’07, pages 1263–1270. AAAI Press.
Shih, W. (1979). A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem. Journal of the Operational Research Society, 30(4):369–378.
Zan, D. and Jaros, J. (2014). Solving the Multidimensional Knapsack Problem using a CUDA accelerated PSO. In IEEE Congress on Evolutionary Computation, CEC 2014, pages 2933–2939.
Publicado
17/10/2023
Como Citar
LEMOS, Dayllon V. X.; LONGO, Humberto J.; MARTINS, Wellington S.; FOULDS, Les R..
A GPU-based DP algorithm for solving multiple instances of the knapsack problem. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 24. , 2023, Porto Alegre/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 265-276.
DOI: https://doi.org/10.5753/wscad.2023.235875.
