by Girlich, E., Hoeding, M., Zaporozhets, A., Chubanov, S..
Series: 2000-32, Preprints
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
lot-sizing problem, greedy algorithm, polymatroid