We study the polyhedral structure of the uncpacitated single-item lot-sizing problem with backlogging. We give an explicit linear description of the convex hull of solutions to this problem in its natural space of production, setup, inventory, and backlogging variables. We describe a separation linear program for our proposed inequalities as well as the first exact combinatorial separation algorithm for a well-known special case. To illustrate the effectiveness of our inequalities, we report a summary of computational experiments with a branch-and-cut algorithm on a class of NP-hard multi-item lot-sizing problems. Finally, we show that our results can be generalized to give strong inequalities for uncapacitated fixed-charge network flow polyhedra that arise in distribution planning problems.

Lunch/refreshments provided.