UKP5: Solving the Unbounded Knapsack Problem

  • Henrique Becker UFRGS
  • Luciana S. Buriol UFRGS

Resumo


Nesse resumo extendido nós apresentamos o UKP5, um algoritmo para solucionar o unbounded knapsack problem (problema da mochila com repetições). O UKP5 é baseado em programação dinâmica, mas implementado de uma forma não-tradicional: ao invés de olhar para trás para usar soluções de subproblemas previamente computados, ele armazena limites inferiores a frente. O UKP5 é consideravelmente mais simples que o EDUK2, o algoritmo do estado da arte para solucionar o problema. Nós executamos o UKP5 e o EDUK2 em uma bateria de testes contendo 4540 instâncias consideradas difíceis pelos autores do EDUK2. Os resultados mostram que o UKP5 é, em média, 47 vezes mais rápido que o EDUK2.


 

Referências

Andonov, R., Poirriez, V., and Rajopadhye, S. (2000). Unbounded knapsack problem: Dynamic programming revisited. European Journal of Operational Research, 123(2):394–407.

Garfinkel, R. S. and Nemhauser, G. L. (1972). Integer programming, volume 4. Wiley New York.

Martello, S. and Toth, P. (1990). An exact algorithm for large unbounded knapsack problems. Operations research letters, 9(1):15–20.

Poirriez, V., Yanev, N., and Andonov, R. (2009). A hybrid algorithm for the unbounded knapsack problem. Discrete Optimization, 6(1):110–124.
Publicado
04/07/2016
BECKER, Henrique; BURIOL, Luciana S.. UKP5: Solving the Unbounded Knapsack Problem. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2016 . p. 828-831. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2016.9835.