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. The problem can also be seen as a single source uncapacitated fixed charge network flow problem on a simple graph. Extended 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, Van Roy and Wolsey [?] for the uncapacitated lot-sizing problem. The convex hull proof is based on showing that an extended facility location formulation is tight and by pro jecting it onto the original space of variables.