A BRANCH AND EXCLUDE ALGORITHM FOR THE KNAPSACK PROBLEM.
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
A branch and exclude algorithm for the solution of the knapsack problem, max summation from i 1 to i N of v sub i x sub i where summation from i 1 to i N of w sub i x sub i or W and x sub i 0,1 is presented which requires relatively small amounts of computer running time and core storage allocation. In addition, a branch and bound scheme is developed. The branch and exclude method is then compared to the branch and bound method and to a branch and bound method given by Kolesar. Computational results are given. Author
- Operations Research