Technical Note—The Multiperiod Knapsack Problem

Bruce H. Faaland
Additional contact information
Bruce H. Faaland: University of Washington, Seattle, Washington

Operations Research, 1981, vol. 29, issue 3, 612-616

Abstract: In the multiperiod knapsack problem the decision maker faces a horizon of m periods. Associated with each period are a number of types of items, each with a value and weight. Subject to the requirement that the cumulative capacity of the knapsack in each period i cannot be exceeded by items chosen in periods 1, …, i , the decision maker chooses the most valuable knapsack possible. A branch and bound algorithm exploits the special structure of the multiperiod knapsack problem by calculating bounds by the direct solution of linear programs with m constraints in 0( m ) operations. Computational experience is reported on problems ranging in size up to 200 constraints and 1,000 general integer variables.

Date: 1981
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.29.3.612 (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:29:y:1981:i:3:p:612-616

Access Statistics for this article

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