This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Levi, R. Articles by Shmoys, D. B. Search for Related Content

Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models

Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
School of Operations Research and Information Engineering and Department of Computer Science, Cornell University, Ithaca, New York 14853
retsef{at}mit.edu
robin{at}orie.cornell.edu
shmoys{at}cs.cornell.edu

In this paper, we consider two fundamental inventory models, the single-period newsvendor problem and its multiperiod extension, but under the assumption that the explicit demand distributions are not known and that the only information available is a set of independent samples drawn from the true distributions. Under the assumption that the demand distributions are given explicitly, these models are well studied and relatively straightforward to solve. However, in most real-life scenarios, the true demand distributions are not available, or they are too complex to work with. Thus, a sampling-driven algorithmic framework is very attractive, both in practice and in theory.

We shall describe how to compute sampling-based policies, that is, policies that are computed based only on observed samples of the demands without any access to, or assumptions on, the true demand distributions. Moreover, we establish bounds on the number of samples required to guarantee that, with high probability, the expected cost of the sampling-based policies is arbitrarily close (i.e., with arbitrarily small relative error) compared to the expected cost of the optimal policies, which have full access to the demand distributions. The bounds that we develop are general, easy to compute, and do not depend at all on the specific demand distributions.

Key Words: inventory; approximation; sampling; algorithms; nonparametric
History: Received: July 21, 2005; revision received: October 25, 2006;

This article has been cited by other articles:

				N. Halman, D. Klabjan, M. Mostagir, J. Orlin, and D. Simchi-Levi A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand Mathematics of Operations Research, August 1, 2009; 34(3): 674 - 685. [Abstract] [PDF]

				W. T. Huh and P. Rusmevichientong A Nonparametric Asymptotic Analysis of Inventory Planning with Censored Demand Mathematics of Operations Research, February 1, 2009; 34(1): 103 - 123. [Abstract] [PDF]

				J. M. Nascimento and W. B. Powell An Optimal Approximate Dynamic Programming Algorithm for the Lagged Asset Acquisition Problem Mathematics of Operations Research, February 1, 2009; 34(1): 210 - 237. [Abstract] [PDF]

				G. Perakis and G. Roels Regret in the Newsvendor Model with Partial Information Operations Research, January 1, 2008; 56(1): 188 - 203. [Abstract] [PDF]