Accession Number:

ADA045529

Title:

Solving Large Zero-One Knapsack Problems.

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1977-07-01

Pagination or Media Count:

36.0

Abstract:

An algorithm for the 0-1 knapsack problem KP is described which relies mainly on three new ideas. The first one is to focus on the core of the problem, namely a knapsack problem equivalent to KP, defined on a particular subset of the variables. The size of this core is usually a small fraction of the full problem size, and does not seem to increase with the latter. While the core cannot be identified without solving KP, a satisfactory approximation can be found by solving LKP, the associated linear program. The second new ingredient is a binary-search-type procedure for solving LKP which, unlike earlier methods, does not require any ordering of the variables. Finally, the third new feature is a simple-minded heuristic whose accracy under certain conditions grows exponentially with the problem size. Computational experience with an algorithm based on the above ideas, on 200 randomly generated test problems with 1,000-10,000 variables and with coefficients ranging from between 10-100 to be between 10-10,000, indicates that for such problems the computational effort grows linearly with the number of variables and logarithmically with the range of coefficients. Total time for the 200 problems was 160 UNIVAC 1108 seconds, and the maximum time for any single problem was 3 seconds.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE