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

The Dynamic and Stochastic Knapsack Problem

Author

Listed:
  • Anton J. Kleywegt

    (Georgia Institute of Technology, Atlanta, Georgia)

  • Jason D. Papastavrou

    (Purdue University, West Lafayette, Indiana)

Abstract

The Dynamic and Stochastic Knapsack Problem (DSKP) is defined as follows. Items arrive according to a Poisson process in time. Each item has a demand (size) for a limited resource (the knapsack) and an associated reward. The resource requirements and rewards are jointly distributed according to a known probability distribution and become known at the time of the item's arrival. Items can be either accepted or rejected. If an item is accepted, the item's reward is received; and if an item is rejected, a penalty is paid. The problem can be stopped at any time, at which time a terminal value is received, which may depend on the amount of resource remaining. Given the waiting cost and the time horizon of the problem, the objective is to determine the optimal policy that maximizes the expected value (rewards minus costs) accumulated. Assuming that all items have equal sizes but random rewards, optimal solutions are derived for a variety of cost structures and time horizons, and recursive algorithms for computing them are developed. Optimal closed-form solutions are obtained for special cases. The DSKP has applications in freight transportation, in scheduling of batch processors, in selling of assets, and in selection of investment projects.

Suggested Citation

  • Anton J. Kleywegt & Jason D. Papastavrou, 1998. "The Dynamic and Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 46(1), pages 17-35, February.
    • Handle: RePEc:inm:oropre:v:46:y:1998:i:1:p:17-35
    DOI: 10.1287/opre.46.1.17
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.46.1.17
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.46.1.17?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. Cyrus Derman & Gerald J. Lieberman & Sheldon M. Ross, 1972. "A Sequential Stochastic Assignment Problem," Management Science, INFORMS, vol. 18(7), pages 349-355, March.
    2. 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.
    3. Toru Nakai, 1986. "A Sequential Stochastic Assignment Problem in a Partially Observable Markov Chain," Mathematics of Operations Research, INFORMS, vol. 11(2), pages 230-240, May.
    4. Lawrence R. Weatherford & Samuel E. Bodily & Phillip E. Pfeifer, 1993. "Modeling the Customer Arrival Process and Comparing Decision Rules in Perishable Asset Revenue Management Situations," Transportation Science, INFORMS, vol. 27(3), pages 239-251, August.
    5. S. L. Brumelle & J. I. McGill & T. H. Oum & K. Sawaki & M. W. Tretheway, 1990. "Allocation of Airline Seats between Stochastically Dependent Demands," Transportation Science, INFORMS, vol. 24(3), pages 183-192, August.
    6. Gregory P. Prastacos, 1983. "Optimal Sequential Investment Decisions Under Conditions of Uncertainty," Management Science, INFORMS, vol. 29(1), pages 118-134, January.
    7. T. J. Stewart, 1981. "The Secretary Problem with an Unknown Number of Options," Operations Research, INFORMS, vol. 29(1), pages 130-145, February.
    8. Rhonda Righter, 1989. "A Resource Allocation Problem in a Random Environment," Operations Research, INFORMS, vol. 37(2), pages 329-338, April.
    9. S. Christian Albright, 1974. "Optimal Sequential Assignments with Random Arrival Times," Management Science, INFORMS, vol. 21(1), pages 60-67, September.
    10. Renwick E. Curry, 1990. "Optimal Airline Seat Allocation with Fare Classes Nested by Origins and Destinations," Transportation Science, INFORMS, vol. 24(3), pages 193-204, August.
    11. Richard D. Wollmer, 1992. "An Airline Seat Management Model for a Single Leg Route When Lower Fare Classes Book First," Operations Research, INFORMS, vol. 40(1), pages 26-37, February.
    12. Mitsushi Tamaki, 1986. "A Generalized Problem of Optimal Selection and Assignment," Operations Research, INFORMS, vol. 34(3), pages 486-493, June.
    13. Marvin Rothstein, 1971. "An Airline Overbooking Model," Transportation Science, INFORMS, vol. 5(2), pages 180-192, May.
    14. John W. Mamer, 1986. "Successive Approximations for Finite Horizon, Semi-Markov Decision Processes with Application to Asset Liquidation," Operations Research, INFORMS, vol. 34(4), pages 638-644, August.
    15. Peter P. Belobaba, 1989. "OR Practice—Application of a Probabilistic Decision Model to Airline Seat Inventory Control," Operations Research, INFORMS, vol. 37(2), pages 183-197, April.
    16. Lawrence W. Robinson, 1995. "Optimal and Approximate Control Policies for Airline Booking with Sequential Nonmonotonic Fare Classes," Operations Research, INFORMS, vol. 43(2), pages 252-263, April.
    17. Lawrence R. Weatherford & Samuel E. Bodily, 1992. "A Taxonomy and Research Overview of Perishable-Asset Revenue Management: Yield Management, Overbooking, and Pricing," Operations Research, INFORMS, vol. 40(5), pages 831-844, October.
    Full references (including those not matched with items on IDEAS)

    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. Syed Asif Raza & Rafi Ashrafi & Ali Akgunduz, 2020. "A bibliometric analysis of revenue management in airline industry," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 19(6), pages 436-465, December.
    2. Chatwin, Richard E., 2000. "Optimal dynamic pricing of perishable products with stochastic demand and a finite set of prices," European Journal of Operational Research, Elsevier, vol. 125(1), pages 149-174, August.
    3. You, Peng-Sheng, 2001. "Airline seat management with rejection-for-possible-upgrade decision," Transportation Research Part B: Methodological, Elsevier, vol. 35(5), pages 507-524, June.
    4. Jeffrey I. McGill & Garrett J. van Ryzin, 1999. "Revenue Management: Research Overview and Prospects," Transportation Science, INFORMS, vol. 33(2), pages 233-256, May.
    5. 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.
    6. Dimitris Bertsimas & Sanne de Boer, 2005. "Simulation-Based Booking Limits for Airline Revenue Management," Operations Research, INFORMS, vol. 53(1), pages 90-106, February.
    7. 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.
    8. You, Peng-Sheng, 2008. "An efficient computational approach for railway booking problems," European Journal of Operational Research, Elsevier, vol. 185(2), pages 811-824, March.
    9. Wen Zhao & Yu-Sheng Zheng, 2001. "A Dynamic Model for Airline Seat Allocation with Passenger Diversion and No-Shows," Transportation Science, INFORMS, vol. 35(1), pages 80-98, February.
    10. Mihai Banciu & Fredrik Ødegaard & Alia Stanciu, 2019. "Distribution-free bounds for the expected marginal seat revenue heuristic with dependent demands," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 18(2), pages 155-163, April.
    11. Badinelli, Ralph D., 2000. "An optimal, dynamic policy for hotel yield management," European Journal of Operational Research, Elsevier, vol. 121(3), pages 476-503, March.
    12. Kavitha Balaiyan & R. K. Amit & Atul Kumar Malik & Xiaodong Luo & Amit Agarwal, 2019. "Joint forecasting for airline pricing and revenue management," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 18(6), pages 465-482, December.
    13. Youyi Feng & Baichun Xiao, 2001. "A Dynamic Airline Seat Inventory Control Model and Its Optimal Policy," Operations Research, INFORMS, vol. 49(6), pages 938-949, December.
    14. 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.
    15. Cynthia Barnhart & Peter Belobaba & Amedeo R. Odoni, 2003. "Applications of Operations Research in the Air Transport Industry," Transportation Science, INFORMS, vol. 37(4), pages 368-391, November.
    16. Peng-Sheng You, 1999. "Dynamic Pricing in Airline Seat Management for Flights with Multiple Flight Legs," Transportation Science, INFORMS, vol. 33(2), pages 192-206, May.
    17. 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.
    18. Youyi Feng & Baichun Xiao, 2000. "Optimal Policies of Yield Management with Multiple Predetermined Prices," Operations Research, INFORMS, vol. 48(2), pages 332-343, April.
    19. Kim, Sang-Won, 2015. "The impact of customer buying behavior on the optimal allocation decisions," International Journal of Production Economics, Elsevier, vol. 163(C), pages 71-88.
    20. de Boer, Sanne V. & Freling, Richard & Piersma, Nanda, 2002. "Mathematical programming for network revenue management revisited," European Journal of Operational Research, Elsevier, vol. 137(1), pages 72-92, February.

    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:46:y:1998:i:1:p:17-35. 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.