Abstract

The lot-sizing polytope is a fundamental structure contained in many practical production planning problems. Here we study this polytope and identify facet-defining inequalities that cut off all fractional extreme points of its linear programming relaxation, as well as liftings from those facets. We give a polynomial-time combinatorial separation algorithm for the inequalities when capacities are constant. We also report computational experiments on solving the lot-sizing problem with varying cost and capacity characteristics. © Springer-Verlag 2003.