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

Grace Lin, Yingdong Lu, David D. Yao

Abstract

The stochastic knapsack problem (SKP) serves as a foundational model for applications ranging from dynamic resource allocation to telecommunication admission control. In recent years, variations of this model have become essential tools for studying revenue management and flexible pricing. This paper investigates a specific class of control known as switch-over policies. Under these policies, a seller initially accepts only high-priced orders and progressively includes lower-priced offers as the decision horizon nears its end. By utilizing a dynamic programming formulation and convex programming to determine optimal switch-over times, we establish the asymptotic optimality of this approach. Furthermore, we develop pricing models to optimize price reductions, demonstrating that simple time-based rules can effectively approximate complex, real-time optimization.

Introduction

In the realm of inventory liquidation—such as a manufacturer selling off leased hardware—the seller faces a classic dilemma: accept a certain but low-value offer now, or wait for a potentially higher-paying buyer who may never arrive. This challenge is formally known as the Stochastic Knapsack Problem. While Dynamic Programming (DP) provides a theoretical path to the optimal solution, it often results in "black box" policies that are difficult to implement. These policies require constant, real-time tracking of every inventory unit and offer little intuitive guidance for long-term pricing strategy.

Lin, Lu, and Yao bridge this gap by proposing switch-over policies. These policies shift the focus from inventory-based triggers to time-based schedules, providing a practical framework that aligns with existing retail markdown strategies while maintaining rigorous mathematical performance.

The Switch-Over Policy Framework

The core logic of a switch-over policy is intuitive: rank potential prices from highest to lowest and set specific times ($t_i$) to expand the range of accepted offers.

  1. Initial Phase: The seller begins by accepting only the highest price class.
  2. Switching Points: At a pre-calculated time $t_1$, the seller "switches over" to accept the top two price classes. At $t_2$, the third class is added, and so on.
  3. The Decision Variable: Instead of monitoring the exact inventory level ($W$) at every second, the manager simply follows a schedule based on the time remaining ($T$).

To determine the optimal switch-over times, the authors transform the problem into a separable convex programming model. This approach is significantly more computationally efficient than traditional DP and remains robust even when buyers request "batches" of items (e.g., a broker purchasing 50 units at once). For these batch arrivals, the authors utilize Markov chains and matrix exponentials to model the depletion of inventory over time.

Theoretical Contributions and Asymptotic Optimality

The most significant theoretical contribution of this research is the proof of asymptotic optimality. The authors demonstrate that as the scale of the problem increases—specifically as inventory ($W$) and the time horizon ($T$) grow—the performance gap between the simple switch-over policy and the perfect DP policy shrinks toward zero.

This is driven by a "Lower-Orthant" structure in the optimal policy: if it is optimal to reject a price at a certain inventory level, it is also optimal to reject it at all lower inventory levels. As the system scales, the "time remaining" becomes the dominant factor in decision-making, rendering precise inventory counts less critical. The authors show that the error rate of the switch-over policy is $O(\sqrt{W})$, meaning that as inventory increases, the relative revenue loss decreases significantly.

Numerical Validation

The paper validates these theoretical findings through extensive numerical simulations using synthetic demand data. Key parameters included:

  • Demand Modeling: Arrivals were modeled as Poisson processes with varying batch sizes (discretized exponential and negative binomial distributions).
  • Price Sensitivity: The models were tested against linear, exponential, and power-law demand functions.

Key Results:

  • Near-Optimal Revenue: In simulations, the switch-over policy consistently achieved revenues within 0.01% to 0.7% of the theoretical maximum.
  • Robustness: The pricing models remained effective even with a limited number of price changes. For example, reducing the number of allowed price levels from eight to three resulted in negligible revenue loss.
  • Scalability: The $\sqrt{W}$ rule was confirmed, showing that larger inventories naturally mitigate the minor inefficiencies of time-based switching.

Practical Implications and Limitations

For practitioners, this research justifies the use of "markdown schedules." It suggests that for large-scale operations, managers do not need to over-invest in complex real-time tracking systems to achieve near-optimal revenue. Instead, they can rely on well-calculated time thresholds.

However, the authors note certain limitations:

  • Small Inventory: For very small-scale problems (e.g., selling a handful of unique items), the asymptotic benefits do not apply, and full DP may still be necessary.
  • Partial Fulfillment: The model assumes an "all-or-nothing" approach to batch orders. If a buyer requests more units than are available, the order is rejected entirely, which may not reflect all real-world retail scenarios.
  • Static Nature: The switch-over times are currently calculated at the start of the horizon. Future iterations could involve "adaptive" switch-over policies that re-calculate times mid-horizon if demand deviates significantly from forecasts.

Conclusion

By revisiting the Stochastic Knapsack Problem through the lens of switch-over policies, Lin, Lu, and Yao provide a mathematically rigorous justification for simple, time-based pricing strategies. Their work demonstrates that in the context of large-scale revenue management, simplicity and optimality are not mutually exclusive.

Summary updated

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 from 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.
BibTeX
@article{lin2008stochastic,
  author = {Grace Lin and Yingdong Lu and David D. Yao},
  title = {{Stochastic Knapsack Problem Revisited: Switch-Over Policies and Dynamic Pricing}},
  journal = {Oper. Res.},
  year = {2008},
  doi = {10.1287/opre.1080.0555},
}
Figure