The Dynamic and Stochastic Knapsack Problem with Deadlines

Jason D. Papastavrou, Srikanth Rajagopalan and Anton J. Kleywegt
Additional contact information
Jason D. Papastavrou: School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907-1287
Srikanth Rajagopalan: School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907-1287
Anton J. Kleywegt: School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907-1287

Management Science, 1996, vol. 42, issue 12, 1706-1718

Abstract: In this paper a dynamic and stochastic model of the well-known knapsack problem is developed and analyzed. The problem is motivated by a wide variety of real-world applications. Objects of random weight and reward arrive according to a stochastic process in time. The weights and rewards associated with the objects are distributed according to a known probability distribution. Each object can either be accepted to be loaded into the knapsack, of known weight capacity, or be rejected. The objective is to determine the optimal policy for loading the knapsack within a fixed time horizon so as to maximize the expected accumulated reward. The optimal decision rules are derived and are shown to exhibit surprising behavior in some cases. It is also shown that if the distribution of the weights is concave, then the decision rules behave according to intuition.

Keywords: dynamic programming; sequential stochastic resource allocation (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.42.12.1706 (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:42:y:1996:i:12:p:1706-1718

Access Statistics for this article

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