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