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

**Series:** 2000-32, Preprints

- MSC:
- 90C05 Linear programming
- 90C10 Integer programming
- 90C27 Combinatorial optimization
- 65K05 Mathematical programming methods

**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