A Lagrangean relaxation algorithm for multi-item lot-sizing problems with joint piecewise linear resource costs

In this paper we study a class of multi-item lot-sizing problems with dynamic demands, as well as lower and upper bounds on a shared resource with a piecewise linear cost. The shared resource might be supply, production or transportation capacity. The model is particularly applicable to problems with joint shipping and/or purchasing cost discounts. The problem is formulated as a mixed-integer program. Lagrangean relaxation is used to decompose the problem into a set of simple sub-problems. A heuristic method based on sub-gradient optimization is then proposed to solve a particular case often encountered in the consumer goods wholesaling and retailing industry. Our tests show that the heuristic proposed is very efficient in solving large real-life supply planning problems.