Lot-size models with backlogging: Strong reformulations and cutting planes (Q1115342)

A production planning problem of an uncapacitated lot-sizing problem with backlogging is dealt with. Special interest is put on investigating effective mixed integer programming reformulations for the problem. Two main approaches are examined. The first is to introduce new variables into the model in order to tighten the formulation. The resulting two reformulations are a facility location model and a shortest path model. Each of these reformulations is shown to be strong in the sense that its LP-relaxation solves the lot-sizing problem. The second approach is to remain in the space of the original variables of the lot-size model. Using the facility location model, an implicit description of the convex hull of solutions can be given, and the problem can be solved as a linear program via a violated cutting plane algorithm. The efficiency of both the shortest path formulation and the cutting plane algorithm are also examined on a series of test problems.