Going faster to see further: graphics processing unit-accelerated value iteration and simulation for perishable...

Area of Science:

• Operations Research
• Computational Science
• Inventory Management

Background:

• Value iteration is effective for perishable inventory problems but computationally intensive due to large state spaces.
• Graphics processing units (GPUs) offer parallel processing capabilities that can accelerate value iteration.
• GPU adoption in operational research lags behind machine learning due to accessibility challenges.

Purpose of the Study:

• To implement and evaluate a GPU-accelerated value iteration method for perishable inventory problems.
• To demonstrate the feasibility of value iteration for previously intractable problem sizes and complexities.
• To compare the performance of GPU-accelerated value iteration policies against heuristic policies.

Main Methods:

• Implemented value iteration and Markov decision process simulators using the JAX library for GPU acceleration.
• Utilized JAX's function transformations and compiler for efficient GPU hardware utilization.
• Developed heuristic policies via simulation optimization in JAX, enabling parallel evaluation of candidate parameters.

Main Results:

• Successfully applied the method to problems with over 16 million states and complex features like product substitution.
• Achieved near-optimal replenishment policies, with heuristic policies showing a maximum optimality gap of 2.49%.
• Demonstrated significant computational speedups, making large-scale value iteration practical.

Conclusions:

• GPU-accelerated value iteration using JAX significantly enhances computational efficiency for perishable inventory management.
• This approach extends the applicability of value iteration to complex, large-scale operational research problems.
• The general methodology is adaptable to various operational research challenges requiring large-scale parallel computation on GPUs.