A Computational Method for Solving the Stochastic Joint Replenishment Problem in High Dimensions

Technical Summary: A Computational Method for Solving the Stochastic Joint Replenishment Problem in High Dimensions

Problem Formulation
The paper addresses the Stochastic Joint Replenishment Problem (SJRP), a classical inventory management challenge involving the coordination of multi-item inventory systems where a fixed replenishment cost is incurred jointly for items ordered together. In the discrete-time formulation considered, a warehouse manager reviews inventory levels periodically and decides whether to place orders for subsets of $d$ items. The system faces random demands, linear holding costs, and backlog penalties. The objective is to minimize the total expected discounted cost over an infinite horizon.

The core difficulty lies in the "curse of dimensionality." Under non-zero fixed replenishment costs, item-level decisions become interdependent, causing the state and decision spaces of the associated Markov Decision Process (MDP) to grow exponentially with the number of items ($d$). Consequently, standard dynamic programming techniques become computationally intractable for high-dimensional settings (e.g., $d \ge 50$), and existing literature has largely relied on heuristic policies with limited theoretical guarantees on optimality.

Methodology
To overcome these computational barriers, the authors propose a novel, simulation-based computational method that bridges discrete-time inventory control with continuous-time impulse control theory and deep learning.

1. Continuous-Time Approximation: The discrete-time SJRP is approximated by a continuous-time impulse control problem. In this formulation, the cumulative demand process is modeled as a Gaussian process (Brownian motion with drift), and the manager can intervene at any time to instantaneously jump the inventory state to a higher level at a fixed cost. This approximation allows for a probabilistic representation of the value function that is more amenable to high-dimensional solution techniques.

2. Probabilistic Representation via Constrained BSDEs: Unlike standard deep Backward Stochastic Differential Equation (BSDE) methods that rely on almost-sure equalities, the value function of this impulse control problem is characterized as the minimal solution to a constrained BSDE. This leads to a stochastic identity involving an almost-sure inequality rather than an equality. Specifically, the value function $V(x)$ is the supremum of values $v$ satisfying a stochastic target condition involving the reference process, the running costs, and the jump costs.

3. Deep Neural Network Solver: The authors develop a computational algorithm to solve this constrained BSDE using deep neural networks.

   • Loss Function: A novel loss function is constructed to handle the inequality constraint. It includes a penalty term for violations of the stochastic inequality, weighted by a tunable penalty parameter $\beta$.
   • Reference Process: A carefully designed reference policy (a randomized order-up-to policy driven by a Poisson process) is used to generate sample paths. This process is engineered to balance exploration and exploitation, ensuring that the neural networks are trained on relevant regions of the state space.
   • Training Strategy: To ensure stability, the authors employ a joint schedule for the penalty parameter $\beta$ and the learning rate. The penalty is gradually increased while the learning rate is decreased, allowing the network to first learn the general structure and then strictly enforce the inequality constraints.

4. Policy Extraction: Once the value function $V$ and its gradient $\nabla V$ are approximated by neural networks, an implementable policy is derived. The policy checks a "no-action" condition derived from the Hamilton-Jacobi-Bellman (HJB) equation. If the condition is violated, an order is placed. The order-up-to vector is determined by minimizing the sum of the approximated value function and the ordering cost, a step that can be pre-computed efficiently.

Key Contributions

• High-Dimensional Scalability: The method successfully solves the SJRP for dimensions up to at least 50 (50 SKUs), a regime where traditional MDP-based optimal solutions are intractable.
• Novel Loss Design: The paper introduces a specific loss function and training schedule tailored to the constrained BSDE framework required for impulse control, addressing the challenge of almost-sure inequalities which standard deep BSDE methods do not handle.
• Reference Process Engineering: The design of the reference process with state-dependent jumps is highlighted as a critical innovation to ensure efficient training and coverage of the relevant state space.
• Implementation: The authors provide a complete pipeline from problem approximation to policy extraction, including detailed hyperparameter tuning strategies and computational results.

Results
The proposed Neural Network (NN) policy was evaluated on 43 test problems across dimensions 2, 12, and 50, with varying demand variability (low, medium, high) and cost structures.

• Low Dimensions ($d=2$): The NN policy was compared against the true optimal policy derived via standard MDP solution techniques. The results show the NN policy performs within 1% of the optimal cost and closely tracks the geometry of the optimal decision boundaries.
• High Dimensions ($d=12$ and $d=50$): Since optimal solutions are intractable, the NN policy was benchmarked against state-of-the-art heuristics: periodic review $(R, S)$, $(Q, S)$, hybrid $(R, Q, S)$, can-order, and independent $(s, S)$ policies.
  • In 12 dimensions, the NN policy matched or outperformed the best benchmark in all cases. In medium- and high-variability settings, it often surpassed the best heuristic by significant margins (e.g., up to 28% improvement over $(R, S)$ in specific high-variability cases).
  • In 50 dimensions, the NN policy consistently beat the best available heuristic across all test cases, with performance gaps reaching up to 5.59%.
• Computational Efficiency: The training time scales modestly with dimension (e.g., ~4 hours for 50 dimensions on a single GPU), avoiding the exponential growth typical of grid-based methods.

Significance and Claims
The paper claims that its method provides a computationally feasible approach to obtaining near-optimal policies for high-dimensional stochastic joint replenishment problems, a long-standing challenge in operations management. By leveraging deep learning to solve the underlying high-dimensional impulse control problem, the authors demonstrate that it is possible to match or exceed the performance of the best existing heuristics without relying on restrictive structural assumptions. The authors note that while the method is currently applied to the SJRP with linear costs and unconstrained order vectors, the framework is generalizable to other impulse control problems, including those in financial engineering (e.g., cash flow management) and supply chains with lead times or lost sales, though these extensions are left for future work. The paper emphasizes that the proposed policy is not merely a heuristic but a data-driven approximation of the optimal control derived from a rigorous probabilistic formulation.