Skip to Main content Skip to Navigation
Journal articles

A lagrangian relaxation approach for supply chain planning with order/setup costs and capacity constraints

Abstract : 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 approximately solved by using the simplex algorithm for linear programming, while Lagrange multipliers are updated by using a surrogate subgradient method that ensures the convergence of the dual problem in case of the approximate resolution of the relaxed problem. At each iteration, a feasible solution of the original problem is constructed from the solution of the relaxed problem. The feasible solution is further improved by a local search that changes the values of two setup variables at each time. By taking the advantages of a special structure of the lot-sizing problem, the local search can be implemented by using a modified simplex algorithm, which significantly reduces its computation time. Numerical experiments show that our approach can find very good solutions for problems of realistic sizes in a short computation time and is more effective than an existing commercial optimization code.
Document type :
Journal articles
Complete list of metadatas
Contributor : Daniel Gavrysiak <>
Submitted on : Thursday, February 13, 2020 - 11:19:55 AM
Last modification on : Wednesday, May 20, 2020 - 3:48:08 PM

Links full text





Haoxun Chen, Chengbin Chu. A lagrangian relaxation approach for supply chain planning with order/setup costs and capacity constraints. Journal of Systems Science and Systems Engineering, Springer Verlag (Germany), 2003, 12 (1), pp.98-110. ⟨10.1007/s11518-006-0123-9⟩. ⟨hal-02477173⟩



Record views