Merging and Sorting Applied to the Zero-One Knapsack Problem

J. H. Ahrens and G. Finke
Additional contact information
J. H. Ahrens: Nova Scotia Technical College, Halifax, Nova Scotia
G. Finke: Nova Scotia Technical College, Halifax, Nova Scotia

Operations Research, 1975, vol. 23, issue 6, 1099-1109

Abstract: Branch-and-bound algorithms are adequate for the solution of a wide range of 0-1 knapsack problems. It is shown that the simplest method of branching is as good as any. However, problems with highly correlated large weights and values quickly become unsolvable in a reasonable time. This paper develops algorithms that are aimed specifically at the hardest possible examples. The new methods use merging and sorting ideas and require a moderate amount of additional memory space. They are, however, faster by factors far in excess of 1,000 in many cases, thereby extending considerably the range of practically solvable 0-1 knapsack problems.

Date: 1975
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.23.6.1099 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:23:y:1975:i:6:p:1099-1109

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().