TWO ALGORITHMS FOR SOLVING THE INDEPENDENT MULTI-DIMENSIONAL KNAPSACK PROBLEM.
Abstract
Two algorithms are presented for solving the multi-dimensional bounded knapsack problem. Algorithm I is an adaptation of the Gilmore-Gomory algorithm for the one dimensional problem. Algorithm II, less compact but probably more efficient, is based upon the structure of the problem. The procedures developed examine the tree of possible solutions, form bounds, and successively narrow-down the tree that will be enumerated to prove optimality of the solution. This algorithm uses linear programming, dominance considerations, marginal-analysis of value, and some heuristics to obtain a very small set of combinations that have to be tried to assure optimality - thus making the algorithm computationally practical on present computers. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1967
- Accession Number
- AD0659996
Entities
People
- Christopher J. Green
Organizations
- Carnegie Institute of Technology