Lot-sizing with fixed charges on stocks: the convex hull

In this paper, we examine a variant of the uncapacitated lot-sizing model of Wagner–Whitin that includes fixed charges on the stocks. Such a model is natural in a production environment where stocking is a complex operation, and appears as a subproblem in more general network design problems. Linear-programming formulations, a dynamic program, the convex hull of integer solutions and a separation algorithm are presented. All these turn out to be very natural extensions of the corresponding results of Barany et al. for the uncapacitated lot-sizing problem. The convex hull proof is based on showing that an extended facility location formulation is tight and by projecting it onto the original space of variables.