Polyhedral Characterization of the Economic Lot-Sizing Problem with Start-up Costs

A class of strong valid inequalities is described for the single-item uncapacitated economic lot-sizing problem with start-up costs. It is shown that these inequalities yield a complete polyhedral characterization of the problem. The corresponding separation problem is formulated as a shortest path problem. Finally, a reformulation as a plant location problem is shown to imply the class of strong valid inequalities, which shows that this reformulation is tight, also.