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. With n the number of periods, we completely characterize the bounded faces of maximal dimension, and derive an O(n2) algorithm to express any point within the polyhedron asa 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 if we optimize over these polyhedra, the face of optimal solutions can be found in O(n2).