A BRANCH AND EXCLUDE ALGORITHM FOR THE KNAPSACK PROBLEM.

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)

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1968
Accession Number
AD0840238

Entities

People

  • Robert Lawrence Hegerich

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computers
  • Core Storage
  • Data Storage Systems
  • Memory Devices

Readers

  • Calculus or Mathematical Analysis
  • Operations Research