https://hal-utt.archives-ouvertes.fr/hal-02477173Chen, HaoxunHaoxunChenLOSI - Laboratoire d'Optimisation des Systèmes Industriels - ICD - Institut Charles Delaunay - UTT - Université de Technologie de Troyes - CNRS - Centre National de la Recherche ScientifiqueChu, ChengbinChengbinChuLOSI - Laboratoire d'Optimisation des Systèmes Industriels - ICD - Institut Charles Delaunay - UTT - Université de Technologie de Troyes - CNRS - Centre National de la Recherche ScientifiqueA lagrangian relaxation approach for supply chain planning with order/setup costs and capacity constraintsHAL CCSD2003Supply chain planninglot sizinglagrangian relaxationlocal searchlinear programmingsimplex algorithm[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]Gavrysiak, Daniel2020-02-13 11:19:552023-02-08 17:11:112020-02-13 11:19:55enJournal articles10.1007/s11518-006-0123-91A 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.