TWO ALGORITHMS FOR SOLVING THE INDEPENDENT MULTI-DIMENSIONAL KNAPSACK PROBLEM.
CARNEGIE INST OF TECH PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
- Operations Research