Name
Abstract | ||
|---|---|---|
We present EDUK, an efficient dynamic programming algorithm for the unbounded knapsack problem. It is based primarily on a new and useful dominance relation, called threshold dominance, which is a strict generalization of all the previously known dominance relations. We show that combining it with a sparse representation of the iteration domain and the periodicity property leads to a drastic reduction of the solution space. We present computational experiments with various data instances to validate our ideas and demonstrate the efficiency of EDUK vis-à-vis the well-known exact algorithm MTU2. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0377-2217(99)00265-9 | European Journal of Operational Research |
Keywords | Field | DocType |
Integer programming,Dominances,Dynamic programming,Periodicity,Combinatorial optimization | Dynamic programming,Mathematical optimization,Exact algorithm,Change-making problem,Continuous knapsack problem,Combinatorial optimization,Integer programming,Cutting stock problem,Knapsack problem,Mathematics | Journal |
Volume | Issue | ISSN |
123 | 2 | 0377-2217 |
Citations | PageRank | References |
54 | 2.95 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rumen Andonov | 1 | 269 | 24.24 |
| Vincent Poirriez | 2 | 89 | 7.64 |
| Sanjay V. Rajopadhye | 3 | 385 | 36.92 |