Reformulations of the shortest route model for dynamic multi-item multi-level capacitated lotsizing

The shortest route representation of the dynamic multi-item multi-level capacitated lotsizing problem is appealing due to the tight bound provided by its Linear Programming (LP) relaxation. However, it suffers from two main drawbacks. Firstly, even solving the LP relaxation of problem instances with up to 16 time periods and 40 items with standard mathematical programming software might require a prohibitive amount of computer time. Secondly, the quadratic growth of the number of variables with the number of periods restricts the solution of problem instances with many periods. Both drawbacks will be addressed in this paper by proposing reformulations of the original shortest route model. Especially we will introduce a model formulation which allows the user to find a trade-off between model size and tightness of the lower bound obtained by the LP relaxation by specifying the number of look ahead periods τ. Furthermore, we will provide an iterative procedure for determining those look ahead periods which result in the tightest LP relaxation. Theoretical insights as well as computational results are provided, too.