New trends in exact algorithms for the \(0-1\) knapsack problem. (English) Zbl 0961.90090
Summary: While the 1980s were focused on the solution of large sized “easy” Knapsack Problems (KPs), this decade has brought several new algorithms, which are able to solve “hard” large sized instances. We will give an overview of the recent techniques for solving hard KPs, with special emphasis on the addition of cardinality constraints, dynamic programming, and rudimentary divisibility. Computational results, comparing all recent algorithms, are presented.
Software:
KnapsackReferences:
| [1] | Balas, E.; Zemel, E., An algorithm for large zero-one knapsack problems, Operations Research, 28, 1130-1154 (1980) · Zbl 0449.90064 |
| [2] | R.E. Bellman, Dynamic Programming, Princeton University Press, Princeton, NJ, 1957; R.E. Bellman, Dynamic Programming, Princeton University Press, Princeton, NJ, 1957 · Zbl 0077.13605 |
| [3] | Dantzig, G. B., Discrete variable extremum problems, Operations Research, 5, 266-277 (1957) · Zbl 1414.90353 |
| [4] | Fayard, D.; Plateau, G., Resolution of the 0-1 knapsack problem: Comparison of methods, Mathematical Programming, 8, 272-307 (1975) · Zbl 0314.90062 |
| [5] | Fayard, D.; Plateau, G., An algorithm for the solution of the 0-1 knapsack problem, Computing, 28, 269-287 (1982) · Zbl 0468.90045 |
| [6] | Freville, A.; Plateau, G., An exact search for the solution of the surrogate dual of the 0-1 bi-dimensional knapsack problem, European Journal of Operational Research, 68, 413-421 (1993) · Zbl 0782.90069 |
| [7] | Horowitz, E.; Sahni, S., Computing partitions with applications to the knapsack problem, Journal of ACM, 21, 277-292 (1974) · Zbl 0329.90046 |
| [8] | S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Management Science 45 (1999) 414-424; S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Management Science 45 (1999) 414-424 · Zbl 1231.90338 |
| [9] | Martello, S.; Toth, P., An upper bound for the zero-one knapsack problem and a branch and bound algorithm, European Journal of Operational Research, 1, 169-175 (1977) · Zbl 0374.90050 |
| [10] | Martello, S.; Toth, P., A new algorithm for the 0-1 knapsack problem, Management Science, 34, 633-644 (1988) · Zbl 0645.90054 |
| [11] | S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, Chichester, UK, 1990; S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, Chichester, UK, 1990 · Zbl 0708.68002 |
| [12] | Martello, S.; Toth, P., Upper bounds and algorithms for hard 0-1 knapsack problems, Operations Research, 45, 768-778 (1997) · Zbl 0902.90125 |
| [13] | Nauss, R. M., An efficient algorithm for the 0-1 knapsack problem, Management Science, 23, 27-31 (1976) · Zbl 0337.90042 |
| [14] | Pisinger, D., An expanding-core algorithm for the exact 0-1 knapsack problem, European Journal of Operational Research, 87, 175-187 (1995) · Zbl 0914.90199 |
| [15] | Pisinger, D., A minimal algorithm for the 0-1 knapsack problem, Operations Research, 45, 758-767 (1997) · Zbl 0902.90126 |
| [16] | Plateau, G.; Elkihel, M., A hybrid method for the 0-1 knapsack problem, Methods of Operations Research, 49, 277-293 (1985) · Zbl 0564.90037 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
