Programação dinâmica paralela em GPU para os problemas da mochila uni e bi-dimensional

  • Dayllon V. X. Lemos UFG
  • Humberto J. Longo UFG
  • Wellington S. Martins UFG

Resumo


O trabalho apresenta algoritmos paralelos de granularidade fina, baseados em programação dinâmica, para a resolução do Problema da Mochila Uni e Bi-Multidimensional. É apresentado também um algoritmo para a resolução conjunta de várias instâncias do problema. Os testes computacionais realizados com implementações dos algoritmos em GPU mostraram um ganho de eficiência considerável, em comparação às suas versões sequenciais.

Palavras-chave: Mochila Multidimensional, Unidade Gráfica de Processamento, MKP, GPU, Programação Dinâmica

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.

Garland, M., Le Grand, S., Nickolls, J., Anderson, J., Hardwick, J., Morton, S., Phillips, E., Zhang, Y., and Volkov, V. (2008). Parallel Computing Experiences with CUDA. IEEE Micro, 28(4):13–27.

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.

Iori, M., de Lima, V. L., Martello, S., and Monaci, M. (2022). 2dpacklib: a two-dimensional cutting and packing library. Optimization Letters, 16:471–480.

Kellerer, H., Pferschy, U., and Pisinger, D. (2004). Knapsack Problems. Springer.

Lorie, J. H. and Savage, L. J. (1955). Three problems in capital rationing. Journal of Business, 28(4):229–239.

Macedo, R., Alves, C., and Carvalho, J. (2010). Arc-flow model for the two-dimensional guillotine cutting stock problem. Computers & OR, 37:991–1001.

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.

Nickolls, J., Buck, I., Garland, M., and Skadron, K. (2008). Scalable Parallel Programming with CUDA: Is CUDA the parallel programming model that application developers have been waiting for? Queue, 6(2):40–53.

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.
Publicado
25/10/2022
LEMOS, Dayllon V. X.; LONGO, Humberto J.; MARTINS, Wellington S.. Programação dinâmica paralela em GPU para os problemas da mochila uni e bi-dimensional. In: ESCOLA REGIONAL DE INFORMÁTICA DE GOIÁS (ERI-GO), 10. , 2022, Goiás. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 24-35. DOI: https://doi.org/10.5753/erigo.2022.227374.