Heuristic policies for stochastic knapsack problem with time‐varying random demand

Yingdong Lu

Abstract

In this paper, we consider the classic stochastic (dynamic) knapsack problem, a fundamental mathematical model in revenue management, with general time-varying random demand. Our main goal is to study the optimal policies, which can be obtained by solving the dynamic programming formulated for the problem, both qualitatively and quantitatively. It is well-known that when the demand size is fixed and the demand distribution is stationary over time, the value function of the dynamic programming exhibits extremely useful first and second order monotonicity properties, which lead to monotonicity properties of the optimal policies. In this paper, we are able to verify that these results still hold even in the case that the price distributions are time-dependent. When we further relax the demand size distribution assumptions and allow them to be arbitrary, for example in random batches, we develop a scheme for using value function of alternative unit demand systems to provide bounds to the value function. These results confirm some of the basic understandings of the stochastic knapsack problem. As a natural consequence, we propose a new class of heuristic policies, two-dimensional switch-over policies, and discuss numerical procedures for optimizing the parameters of the policies. Extensive numerical experiments demonstrate that these switch-over policies can provide performances that are in a close neighborhood of the optimum statistically.

Introduction

The Stochastic Dynamic Knapsack Problem (SDKP) is a cornerstone of revenue management, providing a framework for decision-making under uncertainty. In a typical scenario, such as hotel or airline booking, a manager must decide whether to accept an immediate, lower-paying offer or reserve capacity for a potentially higher-paying customer arriving later. While the stationary version of this problem—where arrival probabilities remain constant—is well-understood, real-world demand is inherently time-varying. For instance, business travelers often book late at higher rates, while leisure travelers book early for discounts. This paper addresses the complexity of finding efficient, near-optimal policies when demand distributions fluctuate over the sales horizon.

Structural Analysis and Mathematical Robustness

A primary contribution of this research is the rigorous proof that the structural properties of the SDKP are resilient to time-varying demand. By formulating the problem through Dynamic Programming (DP) recursions, the author analyzes the "value function"—the maximum expected revenue given a specific state of time and inventory.

The study demonstrates that even under time-dependent price distributions, the value function remains concave and submodular. These properties are critical because they justify the use of monotonic optimal policies; specifically, they confirm that if it is optimal to accept a certain price at a given time and inventory level, it remains optimal to do so if inventory increases or if time progresses (under certain conditions). Furthermore, the paper connects these findings to the concept of multimodularity, a specialized form of discrete convexity that simplifies the optimization of complex queueing and inventory systems.

The Two-Dimensional Switch-over Policy

While solving the full DP provides the theoretical optimum, it is often computationally prohibitive for large-scale systems. To bridge the gap between theory and practice, the author introduces a novel "two-dimensional switch-over" heuristic.

From 1D to 2D

Traditional heuristics often rely on one-dimensional thresholds, typically switching pricing strategies based solely on the time remaining in the horizon. However, such policies are brittle and fail to account for the stochastic nature of inventory depletion. The proposed 2D policy adapts to both remaining time and remaining inventory.

Diffusion Approximation

To optimize the parameters of this 2D policy efficiently, the author employs a diffusion approximation, replacing discrete demand arrivals with a continuous Brownian motion model. By utilizing "first passage time" calculations—mathematical tools used to predict when a moving particle hits a boundary—the policy determines the optimal moments to "switch" from a selective strategy (accepting only high prices) to a more inclusive one as the risk of unsold inventory increases.

Experimental Results

The efficacy of the 2D switch-over policy was evaluated through 125 different system configurations, varying time horizons ($T = 10, 20, 30$), inventory levels, and price classes.

  • Performance Gains: The 2D switch-over policy consistently outperformed standard 1D heuristics by a margin of 5% to 10% in total revenue.
  • Near-Optimality: Statistical simulations revealed that the heuristic's performance frequently reached the 95th percentile of the theoretical optimum calculated via full Dynamic Programming.
  • Computational Efficiency: By leveraging Brownian motion approximations, the heuristic avoids the "curse of dimensionality" associated with DP, making it suitable for real-time applications in large-scale resource management.

Conclusion and Future Directions

This research confirms that the fundamental mathematical intuitions governing the stochastic knapsack problem hold true even in dynamic, time-varying environments. The introduction of the 2D switch-over policy provides a practical, high-performance tool for revenue managers. Future work will focus on extending these heuristics to network revenue management, where multiple interdependent resources (such as connecting flight legs) must be managed simultaneously, and addressing scenarios involving partial fulfillment of large demand batches.

Summary updated

Abstract

Abstract In this paper, we consider the classic stochastic (dynamic) knapsack problem, a fundamental mathematical model in revenue management, with general time‐varying random demand. Our main goal is to study the optimal policies, which can be obtained by solving the dynamic programming formulated for the problem, both qualitatively and quantitatively. It is well known that, when the demand size is fixed and the demand distribution is stationary over time, the value function of the dynamic programming exhibits extremely useful first‐ and second‐order monotonicity properties, which lead to monotonicity properties of the optimal policies. In this paper, we are able to verify that these results still hold even in the case that the price distributions are time dependent. When we further relax the demand size distribution assumptions and allow them to be arbitrary, for example, in random batches, we develop a scheme for using value function of alternative unit demand systems to provide bounds to the value function. These results confirm some of the basic understandings of the stochastic knapsack problem. As a natural consequence, we propose a new class of heuristic policies, two‐dimensional switch‐over policies, and discuss numerical procedures for optimizing the parameters of the policies. Extensive numerical experiments demonstrate that these switch‐over policies can provide performances that are in a close neighborhood of the optimum statistically.
BibTeX
@inproceedings{lu2018heuristic,
  author = {Yingdong Lu},
  title = {{Heuristic policies for stochastic knapsack problem with time‐varying random demand}},
  booktitle = {Applied Stochastic Models in Business and Industry},
  year = {2018},
  doi = {10.1002/asmb.2389},
}
Figure