00-32

A Greedy Algorithm for Capacitated Lot-Sizing Problems

by Girlich, E.; Hoeding, M.; Zaporozhets, A.; Chubanov, S.

 

Preprint series: 00-32, Preprints

MSC:
90C05 Linear programming
90C10 Integer programming
90C27 Combinatorial optimization
65K05 Mathematical programming, See also {90Cxx}

 

Abstract: We show that the convex hull of the set of feasible solutions of single-item capacitated lot-sizing problem (CLSP) is a base polyhedron of a polymatroid and present an O(n) greedy algorithm to solve CLSP with linear objective function. The proposed algorithm is an effective implementation of the classical Edmonds\' algorithm for maximizing linear function over a polymatroid. We consider some special cases of CLSP with nonlinear objective function that can be solved by the proposed greedy algorithm.

Keywords: lot-sizing problem, greedy algorithm, polymatroid


The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.