On the Wagner-Whitin Lot-Sizing Polyhedron

We study a family of unbounded polyhedra arising in the study of uncapacitated lot-sizing problems with Wagner-Whitin costs. We present a new proof of integrality based on completely characterizing the bounded faces of maximal dimension, and in particular showing that they are integral. Withn the number of periods, we derive an O( n2) algorithm to express any point within the polyhedron as a convex combination of extreme points and extreme rays. We also study adjacency on the polyhedra, and give a simple O( n) test for adjacency. Finally we observe that for a given objective function the face of optimal solutions can be found in O( n2).