A Branch and Bound Algorithm for the Knapsack Problem

Peter J. Kolesar
Additional contact information
Peter J. Kolesar: Columbia University

Management Science, 1967, vol. 13, issue 9, 723-735

Abstract: A branch and bound algorithm for solution of the "knapsack problem," max \sum v i x i where \sum w i x i \leqq W and x i - 0, 1, is presented which can obtain either optimal or approximate solutions. Some characteristics of the algorithm are discussed and computational experience is presented. Problems involving 50 items from which approximately 25 items were loaded were solved in an average of 0.07 minutes each by a coded version of this algorithm for the IBM 7094 computer.

Date: 1967
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.13.9.723 (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:ormnsc:v:13:y:1967:i:9:p:723-735

Access Statistics for this article

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