This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Lin, G. Y. Articles by Yao, D. D. Search for Related Content

The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing

IBM Corporation, Yorktown Heights, New York 10598
IBM Corporation, Yorktown Heights, New York 10598
Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
gracelin{at}us.ibm.com
yingdong{at}us.ibm.com
yao{at}ieor.columbia.edu

The stochastic knapsack has been used as a model in wide-ranging applications from dynamic resource allocation to admission control in telecommunication. In recent years, a variation of the model has become a basic tool in studying problems that arise in revenue management and dynamic/flexible pricing, and it is in this context that our study is undertaken. Based on a dynamic programming formulation and associated properties of the value function, we study in this paper a class of control that we call switch-over policies—start by accepting only orders of the highest price, and switch to including lower prices as time goes by, with the switch-over times optimally decided via convex programming. We establish the asymptotic optimality of the switch-over policy, and develop pricing models based on this policy to optimize the price reductions over the decision horizon.

Subject classifications: revenue management; dynamic programming.
History: Received August 2002; revision received April 2006; accepted February 2007.