Asymptotically Optimal Lagrangian Policies for Multi-Warehouse Multi-Store Systems with Lost Sales

We consider a periodic-review inventory control problem for the Multi-Warehouse Multi-Store system with lost sales. We focus on a time horizon during which the system receives no external replenishment. Specifically, each warehouse has a finite initial inventory at the beginning of the horizon, which is then periodically allocated to the stores in each period in order to minimize the total expected lost-sales costs, holding costs, and shipping costs. This is a hard problem and the structure of its optimal policy is extremely complex. We develop simple heuristics based on Lagrangian relaxation that are easy to compute and implement, and have provably near-optimal performances. In particular, we show that the losses of our heuristics are sublinear in both the length of the time horizon and the number of stores. This improves the performance of existing heuristics in the literature whose losses are only sublinear in the number of stores. Numerical study shows that the heuristic performs very well. We also extend our analysis to the setting of positive delivery lead times