IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v56y2008i4p945-957.html
   My bibliography  Save this article

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

Author

Listed:
  • Grace Y. Lin

    (IBM Corporation, Yorktown Heights, New York 10598)

  • Yingdong Lu

    (IBM Corporation, Yorktown Heights, New York 10598)

  • David D. Yao

    (Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027)

Abstract

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.

Suggested Citation

  • Grace Y. Lin & Yingdong Lu & David D. Yao, 2008. "The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing," Operations Research, INFORMS, vol. 56(4), pages 945-957, August.
    • Handle: RePEc:inm:oropre:v:56:y:2008:i:4:p:945-957
    DOI: 10.1287/opre.1080.0555
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1080.0555
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1080.0555?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. William L. Cooper, 2002. "Asymptotic Behavior of an Allocation Policy for Revenue Management," Operations Research, INFORMS, vol. 50(4), pages 720-727, August.
    2. Youyi Feng & Baichun Xiao, 2000. "Optimal Policies of Yield Management with Multiple Predetermined Prices," Operations Research, INFORMS, vol. 48(2), pages 332-343, April.
    3. Youyi Feng & Guillermo Gallego, 1995. "Optimal Starting Times for End-of-Season Sales and Optimal Stopping Times for Promotional Fares," Management Science, INFORMS, vol. 41(8), pages 1371-1391, August.
    4. Shelby Brumelle & Darius Walczak, 2003. "Dynamic Airline Revenue Management with Multiple Semi-Markov Demand," Operations Research, INFORMS, vol. 51(1), pages 137-148, February.
    5. Guillermo Gallego & Garrett van Ryzin, 1997. "A Multiproduct Dynamic Pricing Problem and Its Applications to Network Yield Management," Operations Research, INFORMS, vol. 45(1), pages 24-41, February.
    6. Anton J. Kleywegt & Jason D. Papastavrou, 2001. "The Dynamic and Stochastic Knapsack Problem with Random Sized Items," Operations Research, INFORMS, vol. 49(1), pages 26-41, February.
    7. Cyrus Derman & Gerald J. Lieberman & Sheldon M. Ross, 1972. "A Sequential Stochastic Assignment Problem," Management Science, INFORMS, vol. 18(7), pages 349-355, March.
    8. Tak C. Lee & Marvin Hersh, 1993. "A Model for Dynamic Airline Seat Inventory Control with Multiple Seat Bookings," Transportation Science, INFORMS, vol. 27(3), pages 252-265, August.
    9. Wen Zhao & Yu-Sheng Zheng, 2000. "Optimal Dynamic Pricing for Perishable Assets with Nonhomogeneous Demand," Management Science, INFORMS, vol. 46(3), pages 375-388, March.
    10. Richard Van Slyke & Yi Young, 2000. "Finite Horizon Stochastic Knapsacks with Applications to Yield Management," Operations Research, INFORMS, vol. 48(1), pages 155-172, February.
    11. Gabriel R. Bitran & Susana V. Mondschein, 1995. "An Application of Yield Management to the Hotel Industry Considering Multiple Day Stays," Operations Research, INFORMS, vol. 43(3), pages 427-443, June.
    12. Youyi Feng & Guillermo Gallego, 2000. "Perishable Asset Revenue Management with Markovian Time Dependent Demand Intensities," Management Science, INFORMS, vol. 46(7), pages 941-956, July.
    13. Kalyan Talluri & Garrett van Ryzin, 1999. "A Randomized Linear Programming Method for Computing Network Bid Prices," Transportation Science, INFORMS, vol. 33(2), pages 207-216, May.
    14. Anton J. Kleywegt & Jason D. Papastavrou, 1998. "The Dynamic and Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 46(1), pages 17-35, February.
    15. Constantinos Maglaras & Assaf Zeevi, 2005. "Pricing and Design of Differentiated Services: Approximate Analysis and Structural Insights," Operations Research, INFORMS, vol. 53(2), pages 242-262, April.
    16. Gregory P. Prastacos, 1983. "Optimal Sequential Investment Decisions Under Conditions of Uncertainty," Management Science, INFORMS, vol. 29(1), pages 118-134, January.
    17. Jason D. Papastavrou & Srikanth Rajagopalan & Anton J. Kleywegt, 1996. "The Dynamic and Stochastic Knapsack Problem with Deadlines," Management Science, INFORMS, vol. 42(12), pages 1706-1718, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Belleh Fontem & Megan Price, 2021. "Joint client selection and contract design for a risk-averse commodity broker in a two-echelon supply chain," Annals of Operations Research, Springer, vol. 307(1), pages 111-138, December.
    2. Senay Solak & Armagan Bayram & Mehmet Gumus & Yueran Zhuo, 2019. "Technical Note—Optimizing Foreclosed Housing Acquisitions in Societal Response to Foreclosures," Operations Research, INFORMS, vol. 67(4), pages 950-964, July.
    3. Chen-Ritzo, Ching-Hua & Ervolina, Tom & Harrison, Terry P. & Gupta, Barun, 2011. "Component rationing for available-to-promise scheduling in configure-to-order systems," European Journal of Operational Research, Elsevier, vol. 211(1), pages 57-65, May.
    4. Clifford Stein & Van-Anh Truong & Xinshang Wang, 2020. "Advance Service Reservations with Heterogeneous Customers," Management Science, INFORMS, vol. 66(7), pages 2929-2950, July.
    5. , & , & ,, 2011. "Revenue maximization in the dynamic knapsack problem," Theoretical Economics, Econometric Society, vol. 6(2), May.
    6. Choi, Tsan-Ming & Sethi, Suresh, 2010. "Innovative quick response programs: A review," International Journal of Production Economics, Elsevier, vol. 127(1), pages 1-12, September.
    7. Fabrice Talla Nobibon & Roel Leus, 2014. "Complexity Results and Exact Algorithms for Robust Knapsack Problems," Journal of Optimization Theory and Applications, Springer, vol. 161(2), pages 533-552, May.
    8. Chen, Kai & Ross, Sheldon M., 2014. "An adaptive stochastic knapsack problem," European Journal of Operational Research, Elsevier, vol. 239(3), pages 625-635.
    9. Kai Chen & Sheldon M. Ross, 2014. "The burglar problem with multiple options," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(5), pages 359-364, August.
    10. Stefanie Kosuch & Abdel Lisser, 2010. "Upper bounds for the 0-1 stochastic knapsack problem and a B&B algorithm," Annals of Operations Research, Springer, vol. 176(1), pages 77-93, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Grace Lin & Yingdong Lu & David Yao, 2007. "Stochastic Knapsack Problem Revisited: Switch-Over Policies and Dynamic Pricing," Papers 0708.1146, arXiv.org.
    2. Pak, K. & Piersma, N., 2002. "airline revenue management," ERIM Report Series Research in Management ERS-2002-12-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 University Rotterdam.
    3. Pak, K. & Piersma, N., 2002. "Airline revenue management: an overview of OR techniques 1982-2001," Econometric Institute Research Papers EI 2002-03, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Alec Morton, 2006. "Structural properties of network revenue management models: An economic perspective," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(8), pages 748-760, December.
    5. Gabriel Bitran & René Caldentey, 2003. "An Overview of Pricing Models for Revenue Management," Manufacturing & Service Operations Management, INFORMS, vol. 5(3), pages 203-229, August.
    6. Guillermo Gallego & Michael Z. F. Li & Yan Liu, 2020. "Dynamic Nonlinear Pricing of Inventories over Finite Sales Horizons," Operations Research, INFORMS, vol. 68(3), pages 655-670, May.
    7. Dan Zhang & Larry Weatherford, 2017. "Dynamic Pricing for Network Revenue Management: A New Approach and Application in the Hotel Industry," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 18-35, February.
    8. Jeffrey I. McGill & Garrett J. van Ryzin, 1999. "Revenue Management: Research Overview and Prospects," Transportation Science, INFORMS, vol. 33(2), pages 233-256, May.
    9. William L. Cooper & Tito Homem-de-Mello, 2007. "Some Decomposition Methods for Revenue Management," Transportation Science, INFORMS, vol. 41(3), pages 332-353, August.
    10. Feng, Youyi & Xiao, Baichun, 2006. "A continuous-time seat control model for single-leg flights with no-shows and optimal overbooking upper bound," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1298-1316, October.
    11. Alexander G. Nikolaev & Sheldon H. Jacobson, 2010. "Technical Note ---Stochastic Sequential Decision-Making with a Random Number of Jobs," Operations Research, INFORMS, vol. 58(4-part-1), pages 1023-1027, August.
    12. Kalyan Talluri & Garrett van Ryzin, 2000. "Revenue management under general discrete choice model of consumer behavior," Economics Working Papers 533, Department of Economics and Business, Universitat Pompeu Fabra, revised Oct 2001.
    13. So, Mee Chi & Thomas, Lyn C. & Huang, Bo, 2016. "Lending decisions with limits on capital available: The polygamous marriage problem," European Journal of Operational Research, Elsevier, vol. 249(2), pages 407-416.
    14. Shelby Brumelle & Darius Walczak, 2003. "Dynamic Airline Revenue Management with Multiple Semi-Markov Demand," Operations Research, INFORMS, vol. 51(1), pages 137-148, February.
    15. 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 University Rotterdam.
    16. Maclean, K.D.S. & Ødegaard, F., 2020. "Dynamic capacity allocation for group bookings in live entertainment," European Journal of Operational Research, Elsevier, vol. 287(3), pages 975-988.
    17. Michael N. Katehakis & Yifeng Liu & Jian Yang, 2022. "A revisit to the markup practice of irreversible dynamic pricing," Annals of Operations Research, Springer, vol. 317(1), pages 77-105, October.
    18. Huanan Zhang & Cong Shi & Chao Qin & Cheng Hua, 2016. "Stochastic regret minimization for revenue management problems with nonstationary demands," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(6), pages 433-448, September.
    19. Feng, Youyi & Xiao, Baichun, 2006. "Integration of pricing and capacity allocation for perishable products," European Journal of Operational Research, Elsevier, vol. 168(1), pages 17-34, January.
    20. Kalyan Talluri & Garrett van Ryzin, 2004. "Revenue Management Under a General Discrete Choice Model of Consumer Behavior," Management Science, INFORMS, vol. 50(1), pages 15-33, January.

    More about this item

    Keywords

    revenue management; dynamic programming;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:56:y:2008:i:4:p:945-957. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.