UKP5: Solving the Unbounded Knapsack Problem
Abstract
In this extended abstract we present UKP5, an algorithm for solving the unbounded knapsack problem. UKP5 is based on dynamic programming, but implemented in a non traditional way: instead of looking backward for stored values of subproblems, it stores incremental lower bounds forward. UKP5 is considerably simpler than EDUK2, the state-of-the-art algorithm for solving the problem. We run UKP5 and EDUK2 on a benchmark of 4540 hard instances proposed by the authors of EDUK2. The results reveal that UKP5 outperforms EDUK2, being 47 times faster on the average.
References
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.
Published
2016-07-04
How to Cite
BECKER, Henrique; BURIOL, Luciana S..
UKP5: Solving the Unbounded Knapsack Problem. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
