UKP5: Solving the Unbounded Knapsack Problem
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.
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
Como Citar
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.
