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.