Solving Large Zero-One Knapsack Problems.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1977
- Accession Number
- ADA045529
Entities
People
- Egon Balas
- Eitan Zemel
Organizations
- Carnegie Mellon University