On the Wagner–Whitin lot-sizing polyhedron

On the Wagner–Whitin lot-sizing polyhedron

0.00 Avg rating0 Votes
Article ID: iaor2004948
Country: United States
Volume: 26
Issue: 3
Start Page Number: 591
End Page Number: 600
Publication Date: Aug 2001
Journal: Mathematics of Operations Research
Authors: ,
Keywords: lot sizing
Abstract:

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(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).

Reviews

Required fields are marked *. Your email address will not be published.