Analysis of relaxations for the multi-item capacitated lot-sizing problem

The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. We show that the problem is strongly NP-hard. To explain why one of the most popular among exact and approximate solution methods uses a Lagrangian relaxation of the capacity constraints, we compare this approach with every alternate relaxation of the classical formulation of the problem, to show that it is the most precise in a rigorous sense. The linear relaxation of a shortest path formulation of the same problem has the same value, and one of its Lagrangian relaxations is even more accurate. It is comforting to note that well-known relaxation algorithms based on the traditional formulation can be directly used to solve the shortest path formulation efficiently, and can be further enhanced by new algorithms for the uncapacitated lot-sizing problem. An extensive computational comparison between linear programming, column generation and subgradient optimization exhibits this efficiency, with a surprisingly good performance of column generation. We pinpoint the importance of the data characteristics for an empirical classification of problem difficulty and show that most real-world problems are easier to solve than their randomly generated counterparts because of the presence of initial inventories and their large number of items.