Integrality in Stochastic Inventory Models
Wei Chen, Milind Dawande, Ganesh Janakiraman
Production and Operations Management · 2014 · Volume 23 · Issue 9
Abstract
We study several finite-horizon, discrete-time, dynamic, stochastic inventory control models with integer demands: the newsvendor model, its multi-period extension, and a single-product, multi-echelon assembly model. Equivalent linear programs are formulated for the corresponding stochastic dynamic programs, and integrality results are derived based on the total unimodularity of the constraint matrices. Specifically, for all these models, starting with integer inventory levels, we show that there exist optimal policies that are integral. For the most general single-product, multi-echelon assembly system model, integrality results are also derived for a practical alternative to stochastic dynamic programming, namely,rolling-horizon optimizationby a similar argument. We also present a different approach to prove integrality results for stochastic inventory models. This new approach is based on a generalization we propose for the one-dimensional notion ofpiecewise linearity with integer breakpointsto higher dimensions. The usefulness of this new approach is illustrated by establishing the integrality of both the dynamic programming and rolling-horizon optimization models of a two-product capacitated stochastic inventory control system.
Keywords
integrality, stochastic inventory control, total unimodularity, multi-dimensional piecewise linearity
Enable JavaScript for citation tools and additional paper interactions.