Branch & Cut Methods for Capacitated Lot Sizing

The capacitated lot sizing problem with dynamic demand (CLSP) is NP-hard and in the presence of positive setup times the feasibility problem is NP-complete. Hence, to solve the CLSP heuristics dominate the arena. While a lot of research has been undertaken for the single-level CLSP, the case where precedence constraints among the items have to be taken into account has been tackled by a few authors only. In this contribution we study a branch & cut procedure and solve small instances of the multi-level CLSP with positive setup times optimally.