Dual dynamic programming for linear production/inventory systems

AbstractWe consider the problem of scheduling production of an inventoried item, using a production technology described by a linear program (LP). Traditional approaches involve using LP to find a schedule for a specific starting inventory, or using dynamic programming (DP) to find a production strategy for any stock level at any stage. Our method solves an LP for each period parametrically, and then uses a backwards recursion, based on the marginal conditions of DP, to generate the optimal operating strategy for the entire horizon in a convenient form. This method is dual to conventional DP in the sense that it finds optimal primal variables (points in the state space) corresponding to a set of critical shadow prices, rather than vice versa. It is more accurate and more efficient than traditional DP, while tests indicate that the computational effort required to produce a complete operating strategy is competitive with that taken to produce a single solution via LP. The method also yields useful insights into the nature of the problem. This paper concentrates on a linear deterministic problem with one inventory, but the method can be generalized. It has been successfully applied to two-dimensional reservoir release and coal stockpiling problems under uncertainty