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.
Referências
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.