Linear-programming extended formulations for the single-item lot-sizing problem with backlogging and constant capacity

Recently, several authors 8, 10] have argued for the use of extended formulations to tighten production planning models. In this work we present two linear-programming extended formulations of the constant-capacity lot-sizing problem with backlogging. The first one applies to the problem with a general cost function and has O(n³) variables and constraints. This improves on the more straightforward O(n⁴) Florian and Klein 2] type formulation. The second one applies when the costs satisfy the Wagner-Whitin property but it has O(n²) variables and O(n³) constraints. As a by-product, we positively answer an open question of Miller and Wolsey 4] about the tightness of an extended formulation for the continuous mixing set. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The research was carried out with financial support of the Growth Project G1RD-1999-00034 (LISCOS) of the European Community. The scientific responsibility is assumed by the author.