Abstract
The supply chain management requires increasingly proposals for the production programming planning that brings together its special singularities. Solving coexisting products and alternative processes or by-products must be allowed by the mathematical programming models. The generic materials and operations planning (GMOP) formulation allows operating with different materials and process lists. The paper presents a procedure to solve the versatile GMOP model by the Lagrange Relaxation. The subgradient update method of the lagrangian multiplier is compared with a linear update method. Obtaining lower bound faster compared to the linear method is allowed by the subgradient method, but the linear method provides better solutions after certain iterations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
“Lagrangean” is by the French name of Joseph Louis Lagrange, and “Lagrangian” is by his original Italian name Giuseppe Lodovico Lagrangia.
References
Agmon S (1954) The relaxation method for linear inequalities. Can J Math 6(3):382–392
Araúzo JA, Del-Olmo-Martínez R, Laviós JJ, De-Benito-Martín JJ (2015) Programación y Control de Sistemas de Fabricación Flexibles: un Enfoque Holónico. Rev Iberoam Autom Inf Ind RIAI 12(1):58–68. https://doi.org/10.1016/j.riai.2014.11.005
Attanasio A, Ghiani G, Grandinetti L, Guerriero F (2006) Auction algorithms for decentralized parallel machine scheduling. Parallel Comput 32(9):701–709. https://doi.org/10.1016/j.parco.2006.03.002
Barahona F, Anbil R (2000) The volume algorithm: producing primal solutions with a subgradient method. Math Program 87(3):385–399. https://doi.org/10.1007/s101070050002
Barker CB (1945) The Lagrange multiplier rule for two dependent and two independent variables. Am J Math 67(2):256. https://doi.org/10.2307/2371728
Beltran C, Heredia FJ (2002) Unit commitment by augmented lagrangian relaxation: testing two decomposition approaches. J Optim Theory Appl 112(2):295–314. https://doi.org/10.1023/A:1013601906224
Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4(1):238–252. https://doi.org/10.1007/BF01386316
Bertsekas DP (1975) Nondifferentiable optimization via approximation. In: Mathematical programming study, vol 3, pp 1–25. https://doi.org/10.1007/BFb0120696
Bertsekas DP (1979) Convexification procedures and decomposition methods for nonconvex optimization problems. J Optim Theory Appl 29(2):169–197. https://doi.org/10.1007/BF00937167
Bilde O, Krarup J (1967) Bestemmelse af optimal beliggenhed af produktionssteder. Research reportIMSOR, The Technical University of Denmark, pp 79–88
Bitran GR, Yanasse HH (1982) Computational complexity of the capacitated lot size problem. Manag Sci 28(10):1174–1186. https://doi.org/10.1287/mnsc.28.10.1174
Blouin VY, Lassiter JB, Wiecek MM, Fadel GM (2005) Augmented Lagrangian coordination for decomposed design problems. In: 6th World Congress on structural and multidisciplinary optimization, (June), 1–10
Boyd S, Mutapcic A, Xiao L, Mutapcic A (2008) Subgradient methods. Lecture notes of EE392o, Stanford …, 1, 1–21
Camerini PM, Fratta L, Maffioli F (1975) On improving relaxation methods by modified gradient techniques. Nondiffer Optim 3(August 1974):26–34. https://doi.org/10.1007/BFb0120697
Chang TS (2008) Comments on «surrogate gradient algorithm for Lagrangian relaxation». J Optim Theory Appl 137(3):691–697. https://doi.org/10.1007/s10957-007-9349-z
Conejo AJ, Castillo E, Minguez R, Garcia-Bertrand R (2006) Decomposition techniques in mathematical programming. Springer, Berlin. https://doi.org/10.1007/3-540-27686-6
Coronado-Hernández JR (2016) Análisis del efecto de algunos factores de complejidad e incertidumbre en el rendimiento de las Cadenas de Suministro. Propuesta de una herramienta de valoración basada en simulación. Universitat Politècnica de València, Valencia (Spain). https://doi.org/10.4995/Thesis/10251/61467
Coronado-Hernández JR, Garcia-Sabater JP, Maheut J, Garcia-Sabater J (2010) Modelo de optimización estocástica para la planificación de cadenas de suministro para productos con ciclo de vida cortos. WPOM Work Pap Oper Manag 1(2):1366–1375. https://doi.org/10.4995/wpom.v1i2.785
Coronado-Hernández JR, Simancas-Mateus D, Avila-Martinez K, Garcia-Sabater JP (2017) Heuristic for material and operations planning in supply chains with alternative product structurture. J Eng Appl Sci 12(3):628–635. https://doi.org/10.3923/jeasci.2017.628.635
Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper Res 8(1):101–111. https://doi.org/10.1287/opre.8.1.101
Diabat A, Battaïa O, Nazzal D (2015) An improved Lagrangian relaxation-based heuristic for a joint location-inventory problem. Comput Oper Res 61:170–178. https://doi.org/10.1016/j.cor.2014.03.006
Duchi J, Hazan E, Singer Y (2011) Adaptive subgradient methods for online learning and stochastic optimization. J Mach Learn Res 12:2121–2159. https://doi.org/10.1109/CDC.2012.6426698
Fisher ML (1985) An application oriented guide to Lagrangean relaxation. Interfaces. https://doi.org/10.1287/inte.15.2.10
Fisher ML (2004) The Lagrangian relaxation method for solving integer programming problems. Manag Sci 50(12 Supplement):1861–1871. https://doi.org/10.1287/mnsc.1040.0263
Fisher ML, Lageweg BJ, Lenstra JK, Kan AHGR (1983) Surrogate duality relaxation for job shop scheduling. Discrete Appl Math 5(1):65–75. https://doi.org/10.1016/0166-218X(83)90016-1
Fu YM, Diabat A (2015) A lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem. Appl Math Model 39(3–4):1194–1201. https://doi.org/10.1016/j.apm.2014.07.006
Galvão RD, Marianov V (2011) Lagrangean relaxation-based techniques for solving facility location problems. In: Foundations of location analysis, pp 391–420. https://doi.org/10.1007/978-1-4419-7572-0_17
Garcia-Sabater JP, Maheut J, Marin-Garcia JA (2013) A new formulation technique to model materials and operations planning: the generic materials and operations planning (GMOP) problem. Eur J Ind Eng 7(2):119. https://doi.org/10.1504/EJIE.2013.052572
Gaudioso M, Giallombardo G, Miglionico G (2009) On solving the Lagrangian dual of integer programs via an incremental approach. Comput Optim Appl 44(1):117–138. https://doi.org/10.1007/s10589-007-9149-2
Geoffrion AM (1974) Lagrangean relaxation for integer programming. Approaches Integer Program 2(December):82–114. https://doi.org/10.1007/BFb0120690
Giselsson P, Doan MD, Keviczky T, Schutter B De, Rantzer A (2013) Accelerated gradient methods and dual decomposition in distributed model predictive control. Automatica 49(3):829–833. https://doi.org/10.1016/j.automatica.2013.01.009
Goffin J (1977) On convergence rates of subgradient optimization methods. Math Program 13(1):329–347. https://doi.org/10.1007/BF01584346
Gould S (1945) Lagrange multipliers and functional derterminants. Bull Am Math Soc 52(9):817
Guignard M (2003) Lagrangean relaxation. Soc Estad Investig Oper Top 11(2):151–200. https://doi.org/10.1007/BF02579036
Guignard M, Kim S (1987) Lagrangean decomposition: a model yielding stronger Lagrangean bounds. Math Program 39(2):215–228. https://doi.org/10.1007/BF02592954
Gunnerud V, Foss B (2010) Oil production optimization—a piecewise linear model, solved with two decomposition strategies. Comput Chem Eng 34(11):1803–1812. https://doi.org/10.1016/j.compchemeng.2009.10.019
Gupta A, Maranas CD (1999) A hierarchical Lagrangean relaxation procedure for solving midterm planning problems. Ind Eng Chem Res 38(5):1937–1947. https://doi.org/10.1021/ie980782t
Harb H, Paprott J-N, Matthes P, Schütz T, Streblow R, Mueller D (2015) Decentralized scheduling strategy of heating systems for balancing the residual load. Build Environ 86:132–140. https://doi.org/10.1016/j.buildenv.2014.12.015
Held M, Karp RM (1970) The traveling-salesman problem and minimum spanning trees. Oper Res 18(6):1138–1162. https://doi.org/10.1287/opre.18.6.1138
Held M, Karp RM (1971) The traveling-salesman problem and minimum spanning trees: part II. Math Program 1(1):6–25. https://doi.org/10.1007/BF01584070
Held M, Wolfe P, Crowder HP (1974) Validation of subgradient optimization. Math Program 6(1):62–88. https://doi.org/10.1007/BF01580223
Jeet V, Kutanoglu E (2007) Lagrangian relaxation guided problem space search heuristics for generalized assignment problems. Eur J Oper Res 182(3):1039–1056. https://doi.org/10.1016/j.ejor.2006.09.060
Jeong I-J, Yim S-B (2009) A job shop distributed scheduling based on Lagrangian relaxation to minimise total completion time. Int J Prod Res 47(24):6783–6805. https://doi.org/10.1080/00207540701824217
Karuppiah R, Grossmann IE (2008) A Lagrangean based branch-and-cut algorithm for global optimization of nonconvex mixed-integer nonlinear programs with decomposable structures. J Global Optim 41(2):163–186. https://doi.org/10.1007/s10898-007-9203-8
Kelly JD, Zyngier D (2008) Hierarchical decomposition heuristic for scheduling: coordinated reasoning for decentralized and distributed decision-making problems. Comput Chem Eng 32(11):2684–2705. https://doi.org/10.1016/j.compchemeng.2007.08.007
Kong J, Rönnqvist M (2014) Coordination between strategic forest management and tactical logistic and production planning in the forestry supply chain. Int Trans Oper Res 21(5):703–735. https://doi.org/10.1111/itor.12089
Kuno T, Utsunomiya T (2000) A Lagrangian based branch-and-bound algorithm for production-transportation problems. J Global Optim 18(1):59–73. https://doi.org/10.1023/A:1008373329033
Lau HC, Zhao ZJ, Ge SS, Lee TH (2011) Allocating resources in multiagent flowshops with adaptive auctions. IEEE Trans Autom Sci Eng 8(4):732–743. https://doi.org/10.1109/TASE.2011.2160536
Lemaréchal C (2001) Lagrangian relaxation. Comput Comb Optim 2241:112–156. https://doi.org/10.1007/3-540-45586-8_4
Li Z, Ierapetritou MG (2012) Capacity expansion planning through augmented Lagrangian optimization and scenario decomposition. AIChE J 58(3):871–883. https://doi.org/10.1002/aic.12614
Lidestam H, Rönnqvist M (2011) Use of Lagrangian decomposition in supply chain planning. Math Comput Model 54(9–10):2428–2442. https://doi.org/10.1016/j.mcm.2011.05.054
Lorie JH, Savage LJ (1955) Three problems in rationing capital. J Bus 28(4):229–239. https://doi.org/10.1086/294081
Lu SYP, Lau HYK, Yiu CKF (2012) A hybrid solution to collaborative decision-making in a decentralized supply-chain. J Eng Tech Manag 29(1):95–111. https://doi.org/10.1016/j.jengtecman.2011.09.008
Maheut J (2013) Modelos y Algoritmos Basados en el Concepto Stroke para la Planificación y Programación de Operaciones con Alternativas en Redes de Suministro. Universitat Politècnica de València, Valencia (Spain). https://doi.org/10.4995/Thesis/10251/29290
Maheut J, Garcia-Sabater JP, Mula J (2012) The generic materials and operations planning (GMOP) problem solved iteratively: a case study in multi-site context. IFIP Adv Inf Commun Technol 384 AICT:66–73. https://doi.org/10.1007/978-3-642-33980-6_8
Mao K, Pan QK, Pang X, Chai T (2014) A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process. Eur J Oper Res 236(1):51–60. https://doi.org/10.1016/j.ejor.2013.11.010
Mcdonald CM, Karimi IA (1997) Planning and scheduling of parallel semicontinuous processes. 1. Production planning. Ind Eng Chem Res 36(7):2691–2700. https://doi.org/10.1021/ie960901+
Narciso MG, Lorena LAN (1999) Lagrangean/surrogate relaxation for generalized assignment problems. Eur J Oper Res 114(1):165–177. https://doi.org/10.1016/S0377-2217(98)00038-1
Nedic A, Bertsekas DP (2001) Convergence rate of incremental subgradient algorithms. In: Uryasev S, Pardalos PM (eds) Stochastic optimization: algorithms and applications, pp 223–264
Nishi T, Hiranaka Y, Inuiguchi M (2010) Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness. Comput Oper Res 37(1):189–198. https://doi.org/10.1016/j.cor.2009.04.008
Polyak BT (1969) Minimization of unsmooth functionals. USSR Comput Math Math Phys 9(3):14–29. https://doi.org/10.1016/0041-5553(69)90061-5
Pukkala T, Heinonen T, Kurttila M (2009) An application of a reduced cost approach to spatial forest planning. For Sci 55(1):13–22
Qu T, Nie DX, Chen X, Chen XD, Dai QY, Huang GQ (2015) Optimal configuration of cluster supply chains with augmented Lagrange coordination. Comput Ind Eng 84(SI):43–55. https://doi.org/10.1016/j.cie.2014.12.026
Quddus MA, Ibne Hossain NU, Mohammad M, Jaradat RM, Roni MS (2017) Sustainable network design for multi-purpose pellet processing depots under biomass supply uncertainty. Comput Ind Eng 110:462–483. https://doi.org/10.1016/j.cie.2017.06.001
Sáez J (2000) Solving linear programming relaxations associated with Lagrangean relaxations by Fenchel cutting planes. Eur J Oper Res 121(3):609–626. https://doi.org/10.1016/S0377-2217(99)00056-9
Sherali HD, Choi G (1996) Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs. Oper Res Lett 19(3):105–113. https://doi.org/10.1016/0167-6377(96)00019-3
Sokoler LE, Standardi L, Edlund K, Poulsen NK, Madsen H, Jørgensen JB (2014) A Dantzig–Wolfe decomposition algorithm for linear economic model predictive control of dynamically decoupled subsystems. J Process Control 24(8):1225–1236. https://doi.org/10.1016/j.jprocont.2014.05.013
Stadtler H, Kilger C (2008) Supply chain management and advanced planning. In: Stadtler H, Kilger C (eds) Supply chain management and advanced planning. Concepts, models, software, and case studies. Springer, Berlin
Tosserams S, Etman LFP, Papalambros PY, Rooda JE (2006) An augmented Lagrangian relaxation for analytical target cascading using the alternating direction method of multipliers. Struct Multidiscip Optim 31(3):176–189. https://doi.org/10.1007/s00158-005-0579-0
Vidal-Carreras PI, Garcia-Sabater JP, Coronado-Hernandez JR (2012) Economic lot scheduling with deliberated and controlled coproduction. Eur J Oper Res 219(2):396–404. https://doi.org/10.1016/j.ejor.2011.12.020
Walther G, Schmid E, Spengler TS (2008) Negotiation-based coordination in product recovery networks. Int J Prod Econ 111(2):334–350. https://doi.org/10.1016/j.ijpe.2006.12.069
Wolfe P (1974) Note on a method of conjugate subgradients for minimizing nondifferentiable functions. Math Program 7(1):380–383. https://doi.org/10.1007/BF01585533
Zhang ZH, Jiang H, Pan X (2012) A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain. Int J Prod Econ 140(1):249–255. https://doi.org/10.1016/j.ijpe.2012.01.018
Zhao X, Luh PB, Wang J (1999) Surrogate gradient algorithm for Lagrangian relaxation method. J Optim Theory Appl 100(3):699–712. https://doi.org/10.1023/A:1022646725208
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rius-Sorolla, G., Maheut, J., Coronado-Hernandez, J.R. et al. Lagrangian relaxation of the generic materials and operations planning model. Cent Eur J Oper Res 28, 105–123 (2020). https://doi.org/10.1007/s10100-018-0593-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-018-0593-0