The Dynamic and Stochastic Knapsack Problem with Deadlines
AbstractIn 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by INFORMS in its journal Management Science.
Volume (Year): 42 (1996)
Issue (Month): 12 (December)
dynamic programming; sequential stochastic resource allocation;
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Kang, Seungmo & Ouyang, Yanfeng, 2011. "The traveling purchaser problem with stochastic prices: Exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 209(3), pages 265-272, March.
- Deniz Dizdar & Alex Gershkov & Benny Moldovanu, 2010.
"Revenue Maximization in the Dynamic Knapsack Problem,"
Discussion Paper Series
dp544, The Center for the Study of Rationality, Hebrew University, Jerusalem.
- Moldovanu, Benny & Dizdar, Deniz & Gershkov, Alex, 2011. "Revenue maximization in the dynamic knapsack problem," Theoretical Economics, Econometric Society, vol. 6(2), May.
- Kraft, Edwin R., 2002. "Scheduling railway freight delivery appointments using a bid price approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(2), pages 145-165, February.
- Peter Jacko & Jose Nino-MOra, 2009. "An index for dynamic product promotion and the knapsack problem for perishable items," Statistics and Econometrics Working Papers ws093111, Universidad Carlos III, Departamento de Estadística y Econometría.
- Pak, K. & Dekker, R., 2004. "Cargo Revenue Management: Bid-Prices for a 0-1 Multi Knapsack Problem," ERIM Report Series Research in Management ERS-2004-055-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus Uni.
- Grace Lin & Yingdong Lu & David Yao, 2007. "Stochastic Knapsack Problem Revisited: Switch-Over Policies and Dynamic Pricing," Papers 0708.1146, arXiv.org.
- Wang, Xiubin & Regan, Amelia, 2006. "Dynamic yield management when aircraft assignments are subject to swap," Transportation Research Part B: Methodological, Elsevier, vol. 40(7), pages 563-576, August.
- Florian Zettelmeyer & Fiona Scott Morton & Jorge Silva-Risso, 2006. "Scarcity Rents in Car Retailing: Evidence from Inventory Fluctuations at Dealerships," NBER Working Papers 12177, National Bureau of Economic Research, Inc.
- Zettelmeyer, Florian & Scott Morton, Fiona & Silva-Risso, Jorge, 2005. "Inventory Fluctuations and Price Discrimination: The Determinants of Price Variation in Car Retailing," Department of Economics, Working Paper Series qt6pf5s593, Department of Economics, Institute for Business and Economic Research, UC Berkeley.
- Chiang, David Ming-Huang & Wu, Andy Wei-Di, 2011. "Discrete-order admission ATP model with joint effect of margin and order size in a MTO environment," International Journal of Production Economics, Elsevier, vol. 133(2), pages 761-775, October.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc).
If references are entirely missing, you can add them using this form.