A heuristic approach is developed for supply chain planning modeled as multi-item multi-levelcapacitated lot sizing problems. The heuristic combines Lagrangian relaxation(LR) with local search.Different from existing LR approaches that relax capacity constraints and/or inventory balanceconstraints, our approach only relaxes the technical constraints that each 0-1 setup variable must takevalue 1 if its corresponding continuous variable is positive. The relaxed problem is approximatelysolved by using the simplex algorithm for linear programming, while Lagrange multipliers are updatedby using a surrogate subgradient method that ensures the convergence of the dual problem in case ofthe approximate resolution of the relaxed problem. At each iteration, a feasible solution of the originalproblem is constructed from the solution of the relaxed problem. The feasible solution is furtherimproved by a local search that changes the values of two setup variables at each time. By taking theadvantages of a special stru A heuristic approach is developed for supply chain planning modeled as multi-item multi-level capacitated lot sizing problems. The heuristic combines Lagrangian relaxation (LR) with local search. Different from existing LR approaches that relax capacity constraints and / or inventory balance constraints, our approach only relaxes the technical constraints that each 0-1 setup variable must take value 1 if its corresponding continuous variable is positive. The relaxed problem is approximatelysolved by using the simplex algorithm for linear programming, while Lagrange multipliers are updatedby using a surrogate subgradient method that ensures the at each iteration, a feasible solution of the original problem is constructed from the solution of the relaxed problem. The feasible solution is furtherimproved by a local search that changes the values ​​of two setup variables at each time. By taking theadvantages of a special stru