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) : Hegerich, Robert Lawrence

Report Date : JUN 1968

Pagination or Media Count : 28

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)

Descriptors :   (*MATHEMATICAL PROGRAMMING, PROBLEM SOLVING), OPTIMIZATION, COMBINATORIAL ANALYSIS, FLOW CHARTING, COMPUTER PROGRAMS, ALGORITHMS, THESES.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE