A duality-based relaxation and decomposition approach for inventory distribution systems

We propose a new method for making the inventory replenishment decisions in distribution systems. In particular, we consider distribution systems consisting of multiple retailers that face random demand and a warehouse that supplies the retailers. The method that we propose is based on formulating the distribution problem as a dynamic program, and relaxing the constraints that ensure the nonnegativity of the shipments to the retailers, by associating Lagrange multipliers with them. We show that our method provides lower bounds on the value functions, and a good set of values for the Lagrange multipliers can be obtained by maximizing a concave function in a relatively straightforward manner. Computational experiments indicate that our method can provide significant improvements over the traditional approaches for making the inventory replenishment decisions, in terms of both the tightness of the lower bounds on the value functions and the performance of the policies.