A Lagrangian Relaxation of the Capacitated Multi-Item Lot Sizing Problem Solved with an Interior Point Cutting Plane Algorithm

The capacitated multi-item lot sizing problem consists of finding a production schedule that minimizes over a finite number of periods the total production, holding inventory, and setup costs subject to demand and capacity constraints. The CLSP problem is NP-hard, while the problem of finding a feasible solution, which is polynomial if there are no set-up times, becomes NP-complete when set-up times are included. Approximate solutions can be obtained by heuristics. In this paper we consider an approach based on a Lagrangian relaxation of the capacity constraints. The relaxation is used in two ways. First, it generates a lower bound for the optimal value. Second, the primal and dual solutions of the relaxation (if available) are used to generate integer feasible solutions by primal or dual heuristics. We compare three methods of solving the Lagrangian relaxation: subgradient method, Kelley's cutting plane method -- also known as Dantzig--Wolfe decomposition -- and the analytic center cu..