Lagrange Relaxation for the Capacitated Multi-Item Lot-Sizing Problem

The capacitated multi-item lot-sizing problem, referred to as the CLSP, is to determine the lot sizes of products in each period in a given planning horizon of finite periods, meeting the product demands and resource limits in each period, and to minimize the total cost, consisting of the production, inventory holding, and setup costs. CLSPs are often encountered in industry production settings and they are considered NP-hard. In this paper, we propose a Lagrange relaxation (LR) approach for their solution. This approach relaxes the capacity constraints to the objective function and thus decomposes the CLSP into several uncapacitated single-item problems, each of which can be easily solved by dynamic programming. Feasible solutions are achieved by solving the resulting transportation problems and a fixup heuristic. The Lagrange multipliers in the relaxed problem are updated by using subgradient optimization. The experimental results show that the LR approach explores high-quality solutions and has better applicability compared with other commonly used solution approaches in the literature.