Free Access

The Dynamic and Stochastic Knapsack Problem

Anton J. Kleywegt
Anton J. Kleywegt
Georgia Institute of Technology, Atlanta, Georgia
Search for more papers by this author
,
Jason D. Papastavrou
Jason D. Papastavrou
Purdue University, West Lafayette, Indiana
Search for more papers by this author

Anton J. Kleywegt

Georgia Institute of Technology, Atlanta, Georgia

Search for more papers by this author

Jason D. Papastavrou

Purdue University, West Lafayette, Indiana

Search for more papers by this author

Published Online:1 Feb 1998https://doi.org/10.1287/opre.46.1.17

Supplemental Material

opre.46.1.17-sm.pdf (105 KB)

Cited by
- Shaping Decision Models for Stochastic Dynamic Optimization Problems via Reinforcement Learning
  29 April 2026 | Networks, Vol. 88, No. 1
- Automatic scheduling of satellite tracking tasks by means of policy-gradient reinforcement learning and transformer-based pointer networks
  29 May 2026 | CEAS Space Journal, Vol. 24
- Heuristics for revenue management: an application of the robust knapsack problem
  10 April 2026 | OR Spectrum, Vol. 91
- Optimal resource allocation between the ideation and evaluation phases of the innovation process
  12 January 2026 | The Engineering Economist, Vol. 71, No. 1
- Application of revenue management to satellite communications
  Aerospace Science and Technology, Vol. 168
- A survey of online knapsack problems
  Discrete Applied Mathematics, Vol. 378
- The Crossroads Between Defence Investment Planning and Multi-Period Portfolio Optimization
  IEEE Access, Vol. 14
- Improving the Planning of Stochastic Tasks with Availability Windows Using Prediction
  1 June 2026
- The Competitive Ratio of Threshold Policies for Online Unit-Density Knapsack Problems
  Will Ma,
  David Simchi-Levi,
  Jinglong Zhao
  17 October 2025 | Management Science, Vol. 0, No. 0
- Deep Reinforcement Learning With Integer Optimization for Dynamic Slab Assignment Problem
  IEEE Transactions on Control Systems Technology, Vol. 33, No. 5
- Robust Online Selection with Uncertain Offer Acceptance
  Sebastian Perez-Salazar,
  Mohit Singh,
  Alejandro Toriello
  29 August 2024 | Mathematics of Operations Research, Vol. 50, No. 3
- AoI-Delay Tradeoff in Mobile Edge Caching: A Lyapunov Optimization-Based Method
  IEEE Internet of Things Journal, Vol. 12, No. 11
- Tight Guarantees for Multiunit Prophet Inequalities and Online Stochastic Knapsack
  Jiashuo Jiang; ,
  Will Ma; ,
  Jiawei Zhang
  3 June 2024 | Operations Research, Vol. 73, No. 3
- Dynamic Resource Allocation: Algorithmic Design Principles and Spectrum of Achievable Performances
  Omar Besbes,
  Yash Kanoria,
  Akshit Kumar
  18 November 2024 | Operations Research, Vol. 73, No. 3
- Pricing for Railway Group Tickets in Revenue Management Increasing Revenue and Attracting New Users
  30 October 2025 | Journal of Advanced Transportation, Vol. 2025, No. 1
- Survey of Dynamic Resource-Constrained Reward Collection Problems: Unified Model and Analysis
  Santiago R. Balseiro,
  Omar Besbes,
  Dana Pizarro
  9 May 2023 | Operations Research, Vol. 72, No. 5
- Lunar Infrastructure via Multiscale Granular Stacking
  Journal of Spacecraft and Rockets, Vol. 61, No. 5
- AoI-Delay Tradeoff in Mobile Edge Caching: A Mixed-Order Drift-Plus-Penalty Method
- A deep real options policy for sequential service region design and timing
  Computers & Operations Research, Vol. 161
- Enhancing Knapsack-Based Financial Portfolio Optimization Using Quantum Approximate Optimization Algorithm
  IEEE Access, Vol. 12
- Strategic Decisions Are Rational And Emotional: A Field Experiment Study of Innovation Portfolio Reviews
  1 January 2024 | SSRN Electronic Journal, Vol. 35
- Pseudo-polynomial algorithms for solving the Knapsack Problem with dependencies between items
  Computers & Operations Research, Vol. 158
- Maneuvering the odds: The dynamics of venture capital decision‐making
  10 February 2023 | Strategic Entrepreneurship Journal, Vol. 17, No. 2
- Effective R&D Decision Making in Competitive Environments: A Quantitative Framework
  IEEE Transactions on Engineering Management, Vol. 70, No. 6
- Optimization for Secure and Humane Border Operations
  4 October 2022
- Online generalized assignment problem with historical information
  Computers & Operations Research, Vol. 149
- A novel repositioning approach and analysis for dynamic ride-hailing problems
  EURO Journal on Transportation and Logistics, Vol. 12
- Managing innovation portfolios: From project selection to portfolio design
  1 December 2022 | Production and Operations Management, Vol. 31, No. 12
- Adaptive Bin Packing with Overflow
  Sebastian Perez-Salazar,
  Mohit Singh,
  Alejandro Toriello
  25 February 2022 | Mathematics of Operations Research, Vol. 47, No. 4
- Exact algorithms for the 0–1 Time-Bomb Knapsack Problem
  Computers & Operations Research, Vol. 145
- Data-driven project portfolio selection: Decision-dependent stochastic programming formulations with reliability and time to market requirements
  Computers & Operations Research, Vol. 143
- Stochastic Knapsack Revisited: The Service Level Perspective
  Guodong Lyu,
  Mabel C. Chou,
  Chung-Piaw Teo,
  Zhichao Zheng,
  Yuanguang Zhong
  1 December 2021 | Operations Research, Vol. 70, No. 2
- Reinforcement learning in spacecraft control applications: Advances, prospects, and challenges
  Annual Reviews in Control, Vol. 54
- Managing Innovation Portfolios: From Project Selection to Portfolio Design
  SSRN Electronic Journal, Vol. 28
- Multi-agent reinforcement learning-based dynamic task assignment for vehicles in urban transportation system
  International Journal of Production Economics, Vol. 240
- Dynamic matching with deep reinforcement learning for a two-sided Manufacturing-as-a-Service (MaaS) marketplace
  Manufacturing Letters, Vol. 29
- Q-learning and hyper-heuristic based algorithm recommendation for changing environments
  Engineering Applications of Artificial Intelligence, Vol. 102
- Optimizing pricing and packing of variable-sized cargo
  29 September 2020 | IMA Journal of Management Mathematics, Vol. 32, No. 3
- A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes
  26 June 2020 | Mathematical Programming Computation, Vol. 13, No. 1
- A Near-Optimal Bidding Strategy for Real-Time Display Advertising Auctions
  3 December 2020 | Journal of Marketing Research, Vol. 58, No. 1
- Lunar Infrastructure via Microscale Regolith Assembly
  4 January 2021
- Nonsubmodular Maximization with Knapsack Constraint via Multilinear Extension
  7 February 2021
- Dynamic capacity allocation for group bookings in live entertainment
  European Journal of Operational Research, Vol. 287, No. 3
- A Framework for Managing Innovation
  Stylianos (Stelios) Kavadias,
  Jeremy Hutchison-Krupat
  5 November 2020
- Algorithm for Multi-Robot Chance-Constrained Generalized Assignment Problem with Stochastic Resource Consumption
- Meso-parametric value function approximation for dynamic customer acceptances in delivery routing
  European Journal of Operational Research, Vol. 285, No. 1
- Advance Service Reservations with Heterogeneous Customers
  Clifford Stein,
  Van-Anh Truong,
  Xinshang Wang
  15 October 2019 | Management Science, Vol. 66, No. 7
- A Re-Solving Heuristic with Uniformly Bounded Loss for Network Revenue Management
  Pornpawee Bumpensanti,
  He Wang
  16 March 2020 | Management Science, Vol. 66, No. 7
- Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards
  Alessandro Arlotto,
  Xinchang Xie
  12 June 2020 | Stochastic Systems, Vol. 10, No. 2
- Zombie politics: evolutionary algorithms to counteract the spread of negative opinions
  5 August 2019 | Soft Computing, Vol. 24, No. 1
- A Framework for Managing Innovation
  SSRN Electronic Journal, Vol. 46
- Uniformly Bounded Regret in the Multisecretary Problem
  Alessandro Arlotto,
  Itai Gurvich
  30 August 2019 | Stochastic Systems, Vol. 9, No. 3
- Technical Note—Optimizing Foreclosed Housing Acquisitions in Societal Response to Foreclosures
  Senay Solak,
  Armagan Bayram,
  Mehmet Gumus,
  Yueran Zhuo
  24 June 2019 | Operations Research, Vol. 67, No. 4
- Online scheduling of image satellites based on neural networks and deep reinforcement learning
  Chinese Journal of Aeronautics, Vol. 32, No. 4
- Dynamic pricing for vehicle ferries: Using packing and simulation to optimize revenues
  European Journal of Operational Research, Vol. 273, No. 1
- Single Resource Revenue Management with Independent Demands
  15 August 2019
- A Comparative Study of Meta-Heuristic Optimization Algorithms for 0 – 1 Knapsack Problem: Some Initial Results
  IEEE Access, Vol. 7
- Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes
  SIAM Journal on Optimization, Vol. 29, No. 1
- A Competitive Analysis of Online Knapsack Problems with Unit Density
  SSRN Electronic Journal, Vol. 71
- A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs
  Computers & Operations Research, Vol. 97
- Mathematical programming of airline revenue management with passenger choice behavior
- Seed activation scheduling for influence maximization in social networks
  Omega, Vol. 77
- Dynamic order acceptance and capacity planning in a stochastic multi-project environment with a bottleneck resource
  18 February 2018 | International Journal of Production Research, Vol. 56, No. 1-2
- An overview of revenue management and dynamic pricing models in hotel business
  23 April 2018 | RAIRO - Operations Research, Vol. 52, No. 1
- Online knapsack of unknown capacity
  Theoretical Computer Science, Vol. 697
- The Football Team Composition Problem: a Stochastic Programming approach
  Journal of Quantitative Analysis in Sports, Vol. 13, No. 3
- Higher Prices for Larger Quantities? Nonmonotonic Price–Quantity Relations in B2B Markets
  Wei Zhang,
  Sriram Dasu,
  Reza Ahmadi
  14 July 2016 | Management Science, Vol. 63, No. 7
- Spectrum Auction for Differential Secondary Wireless Service Provisioning With Time-Dependent Valuation Information
  IEEE Transactions on Wireless Communications, Vol. 16, No. 1
- Packing a Knapsack of Unknown Capacity
  SIAM Journal on Discrete Mathematics, Vol. 31, No. 3
- Stochastic Knapsack Revisited: The Service Level Perspective
  SSRN Electronic Journal, Vol. 15
- A Simheuristic approach to the vehicle ferry revenue management problem
- Research and Teaching Opportunities in Project Management
  Nicholas G. Hall
  4 November 2016
- Postponable Acceptance and Assignment: A Stochastic Dynamic Programming Approach
  Keumseok Kang,
  J. George Shanthikumar,
  Kemal Altinkemer
  18 August 2016 | Manufacturing & Service Operations Management, Vol. 18, No. 4
- A decomposition-based heuristic for stochastic emergency routing problems
  Expert Systems with Applications, Vol. 59
- Stochastic regret minimization for revenue management problems with nonstationary demands
  1 September 2016 | Naval Research Logistics (NRL), Vol. 63, No. 6
- Online Network Design with Outliers
  7 July 2015 | Algorithmica, Vol. 76, No. 1
- Robust optimization approach for a chance-constrained binary knapsack problem
  12 July 2015 | Mathematical Programming, Vol. 157, No. 1
- The online knapsack problem with incremental capacity
  30 December 2015 | Mathematical Methods of Operations Research, Vol. 83, No. 2
- Lending decisions with limits on capital available: The polygamous marriage problem
  European Journal of Operational Research, Vol. 249, No. 2
- Dynamic product portfolio management with life cycle considerations
  International Journal of Production Economics, Vol. 171
- Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes
  SIAM Journal on Optimization, Vol. 26, No. 3
- Confidence-based reasoning in stochastic constraint programming
  Artificial Intelligence, Vol. 228
- STATIC STOCHASTIC KNAPSACK PROBLEMS
  16 October 2015 | Probability in the Engineering and Informational Sciences, Vol. 29, No. 4
- Stage- and scenario-wise Fenchel decomposition for stochastic mixed 0-1 programs with special structure
  Computers & Operations Research, Vol. 59
- Managing Underperformance Risk in Project Portfolio Selection
  Nicholas G. Hall,
  Daniel Zhuoyu Long,
  Jin Qi,
  Melvyn Sim
  8 June 2015 | Operations Research, Vol. 63, No. 3
- The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options
  15 May 2015 | Naval Research Logistics (NRL), Vol. 62, No. 4
- A Methodology Based on Evolutionary Algorithms to Solve a Dynamic Pickup and Delivery Problem Under a Hybrid Predictive Control Approach
  Diego Muñoz-Carpintero,
  Doris Sáez,
  Cristián E. Cortés,
  Alfredo Núñez
  10 March 2015 | Transportation Science, Vol. 49, No. 2
- An Approximate Dynamic Programming heuristic to support non-strategic project selection for the Royal Canadian Navy
  8 November 2013 | The Journal of Defense Modeling and Simulation: Applications, Methodology, Technology, Vol. 12, No. 2
- Shared execution of recurring workloads in MapReduce
  1 February 2015 | Proceedings of the VLDB Endowment, Vol. 8, No. 7
- Literature Review
  4 February 2014
- Online Knapsack of Unknown Capacity:
  20 June 2015
- A Dynamic-Oriented Decision Support System for Group Interview Knapsack Problem
  15 August 2015
- Ten Times Eighteen
  Journal of Information Processing, Vol. 23, No. 3
- Dynamic Demand Forecasting and Ticket Assignment for High-Speed Rail Revenue Management in China
  1 January 2015 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 2475, No. 1
- An adaptive stochastic knapsack problem
  European Journal of Operational Research, Vol. 239, No. 3
- The burglar problem with multiple options
  16 June 2014 | Naval Research Logistics (NRL), Vol. 61, No. 5
- An improved firefly algorithm for solving dynamic multidimensional knapsack problems
  Expert Systems with Applications, Vol. 41, No. 8
- Complexity Results and Exact Algorithms for Robust Knapsack Problems
  11 May 2013 | Journal of Optimization Theory and Applications, Vol. 161, No. 2
- Dynamic scheduling with due dates and time windows: an application to chemotherapy patient appointment booking
  10 October 2013 | Health Care Management Science, Vol. 17, No. 1
- A Dynamic Approach for the Online Knapsack Problem
- Introduction
  23 August 2012
- THE SEQUENTIAL STOCHASTIC ASSIGNMENT PROBLEM WITH POSTPONEMENT OPTIONS
  10 December 2012 | Probability in the Engineering and Informational Sciences, Vol. 27, No. 1
- Optimizing the Configuration of Development Teams Using EVA
- Information in Fleeting Opportunities
- A single-resource revenue management problem with random resource consumptions
  21 December 2017 | Journal of the Operational Research Society, Vol. 63, No. 9
- Revenue Management for Cloud Providers--A Policy-Based Approach under Stochastic Demand
- An Optimization Model of the Single‐Leg Air Cargo Space Control Based on Markov Decision Process
  26 November 2012 | Journal of Applied Mathematics, Vol. 2012, No. 1
- The Character and Variety of the Term of Borrowed Scenery in Japanese Gardening
  Landscape Research Japan Online, Vol. 5
- A review on stochastic models and analysis of warehouse operations
  11 June 2011 | Logistics Research, Vol. 3, No. 4
- Discrete-order admission ATP model with joint effect of margin and order size in a MTO environment
  International Journal of Production Economics, Vol. 133, No. 2
- Improving LTL truck load utilization on line
  European Journal of Operational Research, Vol. 210, No. 2
- Knapsack problem with probability constraints
  1 July 2010 | Journal of Global Optimization, Vol. 49, No. 3
- Sequential stochastic assignment under uncertainty: estimation and convergence
  6 January 2011 | Statistical Inference for Stochastic Processes, Vol. 14, No. 1
- Critical Level Policies in Lost Sales Inventory Systems with Different Demand Classes
- Complexity Results and Exact Algorithms for Robust Knapsack Problems
  SSRN Electronic Journal, Vol. 15
- Optimizing the Configuration of Development Teams Using EVA
  International Journal of Information Technology Project Management, Vol. 2, No. 1
- Information in Fleeting Opportunities
  International Journal of Operations Research and Information Systems, Vol. 2, No. 1
- A Lagrangian approach to Dynamic Resource Allocation
- Planning in logistics
  28 September 2010
- Technical Note—Stochastic Sequential Decision-Making with a Random Number of Jobs
  Alexander G. Nikolaev,
  Sheldon H. Jacobson,
  5 February 2010 | Operations Research, Vol. 58, No. 4-part-1
- Dynamic Assignment of Flexible Service Resources
  1 May 2010 | Production and Operations Management, Vol. 19, No. 3
- Online Network Design with Outliers
- USING ORDER ADMISSION CONTROL TO MAXIMIZE REVENUE UNDER CAPACITY UTILIZATION REQUIREMENTS IN MTO B2B INDUSTRIES
  Journal of the Operations Research Society of Japan, Vol. 53, No. 4
- A Single-Resource Revenue Management Problem with Random Resource Consumptions
  SSRN Electronic Journal, Vol. 41
- Mid-Cycle Capital Planning Optimization
  The Engineering Economist, Vol. 54, No. 3
- A single-resource allocation problem with Poisson resource requirements
  5 July 2009 | Optimization Letters, Vol. 3, No. 4
- An approximate dynamic programming approach to solving a dynamic, stochastic multiple knapsack problem
  3 April 2009 | International Transactions in Operational Research, Vol. 16, No. 3
- On Unbounded Zero-One Knapsack With Discrete-Sized Objects
  11 July 2015 | International Journal of Computers and Applications, Vol. 31, No. 2
- Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering
  Computers & Operations Research, Vol. 35, No. 11
- The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing
  Grace Y. Lin,
  Yingdong Lu,
  David D. Yao,
  1 August 2008 | Operations Research, Vol. 56, No. 4
- Online auctions and generalized secretary problems
  1 June 2008 | ACM SIGecom Exchanges, Vol. 7, No. 2
- Hybrid adaptive predictive control for a dynamic pickup and delivery problem including traffic congestion
  15 October 2007 | International Journal of Adaptive Control and Signal Processing, Vol. 22, No. 2
- Dynamic order acceptance and capacity planning on a single bottleneck resource
  5 October 2007 | Naval Research Logistics (NRL), Vol. 54, No. 8
- Some Decomposition Methods for Revenue Management
  William L. Cooper,
  Tito Homem-de-Mello,
  1 August 2007 | Transportation Science, Vol. 41, No. 3
- Pricing and Capacity Rationing for Rentals with Uncertain Durations
  Noah Gans,
  Sergei Savin,
  1 March 2007 | Management Science, Vol. 53, No. 3
- Time-Constrained Restless Bandits and the Knapsack Problem for Perishable Items (Extended Abstract)
  Electronic Notes in Discrete Mathematics, Vol. 28
- O&D revenue management in cargo airlines—a mathematical programming approach
- Structural properties of network revenue management models: An economic perspective
  12 June 2006 | Naval Research Logistics (NRL), Vol. 53, No. 8
- O&D revenue management in cargo airlines—a mathematical programming approach
  8 February 2006 | OR Spectrum, Vol. 29, No. 1
- Revenue management in make-to-order manufacturing—an application to the iron and steel industry
  23 December 2005 | OR Spectrum, Vol. 29, No. 1
- Semi-Markov information model for revenue management and dynamic pricing
  9 March 2006 | OR Spectrum, Vol. 29, No. 1
- A continuous-time seat control model for single-leg flights with no-shows and optimal overbooking upper bound
  European Journal of Operational Research, Vol. 174, No. 2
- Modeling high demand variance in dynamic programming
  6 September 2006 | Journal of Revenue and Pricing Management, Vol. 5, No. 2
- Online pricing for web service providers
  27 May 2006
- Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching
  Soumia Ichoua,
  Michel Gendreau,
  Jean-Yves Potvin,
  1 May 2006 | Transportation Science, Vol. 40, No. 2
- A Case-Based Seat Allocation System for Airline Revenue Management
- An Application of Markov Decision Processes to the Seat Inventory Control Problem
- The Strategy of Inventory Control with Consideration of Channels Research
- Dynamic Order Acceptance and Capacity Planning within a Multi-Project Environment
  SSRN Electronic Journal, Vol. 41
- Solving a dynamic resource allocation problem through continuous optimization
  IEEE Transactions on Automatic Control, Vol. 50, No. 6
- Simulation Optimization Using Tabu Search: An Emprical Study
- Stochastic Networks: Admission and Routing Using Penalty Functions
  Queueing Systems, Vol. 48, No. 3-4
- Node-Level Energy Management for Sensor Networks in the Presence of Multiple Applications
  Wireless Networks, Vol. 10, No. 6
- Revenue Management Under a General Discrete Choice Model of Consumer Behavior
  Kalyan Talluri,
  Garrett van Ryzin,
  1 January 2004 | Management Science, Vol. 50, No. 1
- Dynamic Airline Revenue Management with Multiple Semi-Markov Demand
  Shelby Brumelle,
  Darius Walczak,
  1 February 2003 | Operations Research, Vol. 51, No. 1
- Revenue Management
- Optimal Airline Booking Control with Cancellations
- Pricing of Multidimensional Resources in Revenue Management (Multidimensional Dynamic Stochastic Knapsack Problem)
- Node-level energy management for sensor networks in the presence of multiple applications
- A time-dependent multiple criteria single-machine scheduling problem
  European Journal of Operational Research, Vol. 135, No. 1
- The Dynamic and Stochastic Knapsack Problem with Random Sized Items
  Anton J. Kleywegt,
  Jason D. Papastavrou,
  1 February 2001 | Operations Research, Vol. 49, No. 1
- 0-1 Knapsack Problems with Random Budgets
  SSRN Electronic Journal, Vol. 2
- A Discrete Choice Model of Yield Management
  SSRN Electronic Journal, Vol. 5
- Finite Horizon Stochastic Knapsacks with Applications to Yield Management
  Richard Van Slyke,
  Yi Young,
  1 February 2000 | Operations Research, Vol. 48, No. 1
- Dynamic programming approaches to the multiple criteria knapsack problem
  13 January 2000 | Naval Research Logistics (NRL), Vol. 47, No. 1
- Revenue Management: Research Overview and Prospects
  Jeffrey I. McGill,
  Garrett J. van Ryzin,
  1 May 1999 | Transportation Science, Vol. 33, No. 2

Volume 46, Issue 1

January-February 1998

Pages 1-158

Article Information

Supplemental Material

Metrics

Information

Published Online:February 01, 1998

Cite as

Anton J. Kleywegt, Jason D. Papastavrou, (1998) The Dynamic and Stochastic Knapsack Problem. Operations Research 46(1):17-35.

https://doi.org/10.1287/opre.46.1.17

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

The Dynamic and Stochastic Knapsack Problem

Supplemental Material

Volume 46, Issue 1

Article Information

Supplemental Material

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News