Programação dinâmica paralela em GPU para os problemas da mochila uni e bi-dimensional
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.
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
Como Citar
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.
