Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959503 | European Journal of Operational Research | 2017 | 28 Pages |
Abstract
Given a set of items with profits and weights and a knapsack capacity, we study the problem of finding a maximal knapsack packing that minimizes the profit of the selected items. We propose an effective dynamic programming (DP) algorithm which has a pseudo-polynomial time complexity. We demonstrate the equivalence between this problem and the problem of finding a minimal knapsack cover that maximizes the profit of the selected items. In an extensive computational study on a large and diverse set of benchmark instances, we demonstrate that the new DP algorithm outperforms a state-of-the-art commercial mixed-integer programming (MIP) solver applied to the two best performing MIP models from the literature.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Fabio Furini, Ivana LjubiÄ, Markus Sinnl,