Back to Search
Start Over
A NEW ALGORITHM FOR THE 0-1 KNAPSACK PROBLEM.
- Source :
- Management Science; May88, Vol. 34 Issue 5, p633-644, 12p
- Publication Year :
- 1988
-
Abstract
- We present a new algorithm for the optimal solution of the 0-1 Knapsack problem, which is particularly effective for large-size problems. The algorithm is based on determination of an appropriate small subset of items and the solution of the corresponding "core problem": from this we derive a heuristic solution for the original problem which, with high probability, can be proved to be optimal. The algorithm incorporates a new method of computation of upper bounds and efficient implementations of reduction procedures. The corresponding Fortran code is available. We report computational experiments on small-size and large-size random problems, comparing the proposed code with all those available in the literature. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00251909
- Volume :
- 34
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- Management Science
- Publication Type :
- Academic Journal
- Accession number :
- 7162832
- Full Text :
- https://doi.org/10.1287/mnsc.34.5.633