Accession Number:

AD0840238

Title:

A BRANCH AND EXCLUDE ALGORITHM FOR THE KNAPSACK PROBLEM.

Descriptive Note:

Master's thesis,

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1968-06-01

Pagination or Media Count:

28.0

Abstract:

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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE