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. With n the number of periods, we derive an O(n²) 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(n²).