LP-based heuristics for the capacitated lot-sizing problem: The interaction of model formulation and solution algorithm

We consider here the application of trivial LP-based rounding heuristics to the capacitated lot-sizing problem (CLSP). The motivation behind the use of LP-based heuristics is that their extension to cope with complicating features (to be expected, for example, when dealing with a master production scheduling problem within a material requirements planning system) is generally easier than with alternative approaches such as lagrangian relaxation. It is well known that strong model formulations, like the Plant Location Formulation (PLF) or the Shortest Path Formulation (SPF), are needed to obtain good results when working on a CLSP. Still, from a practical point of view, a few questions deserve investigation. First, the relative performance of PLF and SPF should be assessed. Second, given the increased size of the more complicated formulations, the possible benefits of using interior point methods must be considered. Third, the sensitivity of the computation times with respect to the characteristics of problem instances should be evaluated. We report some computational experiments on relatively large problems (500 items and 15 time buckets, resulting in 7500 binary variables). For the simple CLSP model, trivial heuristics can yield near-optimal solutions with a reasonable computational effort, at least for the problem instances we consider. However, there is a critical and non-obvious interaction between the model formulation, the problem instance characteristics, and the solution algorithm.