An adaptive, distribution-free algorithm for the newsvendor problem with censored demands, with applications to inventory and distribution

We consider the problem of optimizing inventories for problems where the de mand distribution is unknown, and where it does not necessarily follow a st andard form such as the normal. We address problems where the process of de ciding the inventory, and then realizing the demand, occurs repeatedly. The only information we use is the amount of inventory left over. Rather than attempting to estimate the demand distribution, we directly estimate the va lue function using a technique called the Concave, Adaptive Value Estimatio n (CAVE) algorithm. CAVE constructs a sequence of concave piecewise linear approximations using sample gradients of the recourse function at different points in the domain. Since it is a sampling-based method, CAVE does not r equire knowledge of the underlying sample distribution. The result is a non linear approximation that is more responsive than traditional linear stocha stic quasi-gradient methods and more flexible than analytical techniques th at require distribution information. In addition, we demonstrate near-optim al behavior of the CAVE approximation in experiments involving two differen t types of stochastic programs the newsvendor stochastic inventory problem and two-stage distribution problems.