Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems

The paper shows that a broad class of problems can be formulated as minimizing a concave function over the solution set of a Leontief substitution system. The class includes deterministic single- and multi-facility economic lot size, lot-size smoothing, warehousing, product-assortment, batch-queuing, capacity-expansion, investment consumption, and reservoir-control problems with concave cost functions. Because in such problems an optimum occurs at an extreme point of the solution set, we can utilize the characterization of the extreme points given in a companion paper to obtain most existing qualitative characterizations of optimal policies for inventory models with concave costs in a unified manner. Dynamic programming recursions for searching the extreme points to find an optimal point are given in a number of cases. We only give algorithms whose computational effort increases algebraically (instead of exponentially) with the size of the problem.