THE KNAPSACK PROBLEM: SOME RELATIONS FOR AN IMPROVED ALGORITHM

Abstract

The knapsack problem has traditionally been solved by dynamic programming, though a more recent enumerative algorithm by P. C. Gilmore and R. E. Gomory has proved somewhat more efficient. In this paper relations are developed which substantially reduce the number of solutions which must be examined by the Gilmore-Gomory method, or by any algorithm for the knapsack problem which uses an enumerative base. Our results enable certain problems for which the Gilmore-Gomory method reduces almost to complete enumeration to be solved after examining only a handful of alternatives. Computer studies to provide detailed comparisons of methods which do and do not employ these results have not yet been undertaken.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1965
Accession Number
AD0610380

Entities

People

  • Fred Glover

Organizations

  • Carnegie Institute of Technology

Tags

Communities of Interest

  • Autonomy
  • Human Systems
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computers
  • Dynamic Programming
  • Hard Copy
  • Heuristic Methods
  • Linear Programming
  • Paper
  • Paper Industry

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Operations Research
  • Theoretical Analysis.