Lagrangian relaxation of the Generic Materials and Operations Planning model

[EN] 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.Rius-Sorolla, G.; Maheut, J.; Coronado-Hernandez, J.; García Sabater, JP. (2020). Lagrangian relaxation of the Generic Materials and Operations Planning model. Central European Journal of Operations Research. 28:105-123. https://doi.org/10.1007/s10100-018-0593-010512328Agmon S (1954) The relaxation method for linear inequalities. Can J Math 6(3):382–392Araú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.005Attanasio 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.002Barahona 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/s101070050002Barker CB (1945) The Lagrange multiplier rule for two dependent and two independent variables. Am J Math 67(2):256. https://doi.org/10.2307/2371728Beltran 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:1013601906224Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4(1):238–252. https://doi.org/10.1007/BF01386316Bertsekas DP (1975) Nondifferentiable optimization via approximation. In: Mathematical programming study, vol 3, pp 1–25. https://doi.org/10.1007/BFb0120696Bertsekas DP (1979) Convexification procedures and decomposition methods for nonconvex optimization problems. J Optim Theory Appl 29(2):169–197. https://doi.org/10.1007/BF00937167Bilde O, Krarup J (1967) Bestemmelse af optimal beliggenhed af produktionssteder. Research reportIMSOR, The Technical University of Denmark, pp 79–88Bitran 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.1174Blouin 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–10Boyd S, Mutapcic A, Xiao L, Mutapcic A (2008) Subgradient methods. Lecture notes of EE392o, Stanford …, 1, 1–21Camerini 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/BFb0120697Chang 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-zConejo AJ, Castillo E, Minguez R, Garcia-Bertrand R (2006) Decomposition techniques in mathematical programming. Springer, Berlin. https://doi.org/10.1007/3-540-27686-6Coronado-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/61467Coronado-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.785Coronado-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.635Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper Res 8(1):101–111. https://doi.org/10.1287/opre.8.1.101Diabat 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.006Duchi 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.6426698Fisher ML (1985) An application oriented guide to Lagrangean relaxation. Interfaces. https://doi.org/10.1287/inte.15.2.10Fisher 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.0263Fisher 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-1Fu 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.006Galvã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_17Garcia-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.052572Gaudioso 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-2Geoffrion AM (1974) Lagrangean relaxation for integer programming. Approaches Integer Program 2(December):82–114. https://doi.org/10.1007/BFb0120690Giselsson 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.009Goffin J (1977) On convergence rates of subgradient optimization methods. Math Program 13(1):329–347. https://doi.org/10.1007/BF01584346Gould S (1945) Lagrange multipliers and functional derterminants. Bull Am Math Soc 52(9):817Guignard M (2003) Lagrangean relaxation. Soc Estad Investig Oper Top 11(2):151–200. https://doi.org/10.1007/BF02579036Guignard M, Kim S (1987) Lagrangean decomposition: a model yielding stronger Lagrangean bounds. Math Program 39(2):215–228. https://doi.org/10.1007/BF02592954Gunnerud 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.019Gupta 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/ie980782tHarb 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.015Held 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.1138Held 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/BF01584070Held M, Wolfe P, Crowder HP (1974) Validation of subgradient optimization. Math Program 6(1):62–88. https://doi.org/10.1007/BF01580223Jeet 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.060Jeong 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/00207540701824217Karuppiah 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-8Kelly 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.007Kong 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.12089Kuno 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:1008373329033Lau 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.2160536Lemaréchal C (2001) Lagrangian relaxation. Comput Comb Optim 2241:112–156. https://doi.org/10.1007/3-540-45586-8_4Li 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.12614Lidestam 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.054Lorie JH, Savage LJ (1955) Three problems in rationing capital. J Bus 28(4):229–239. https://doi.org/10.1086/294081Lu 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.008Maheut 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/29290Maheut 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_8Mao 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.010Mcdonald 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-1Nedic A, Bertsekas DP (2001) Convergence rate of incremental subgradient algorithms. In: Uryasev S, Pardalos PM (eds) Stochastic optimization: algorithms and applications, pp 223–264Nishi 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.008Polyak BT (1969) Minimization of unsmooth functionals. USSR Comput Math Math Phys 9(3):14–29. https://doi.org/10.1016/0041-5553(69)90061-5Pukkala T, Heinonen T, Kurttila M (2009) An application of a reduced cost approach to spatial forest planning. For Sci 55(1):13–22Qu 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.026Quddus 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.001Sá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-9Sherali 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-3Sokoler 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.013Stadtler 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, BerlinTosserams 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-0Vidal-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.020Walther 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.069Wolfe P (1974) Note on a method of conjugate subgradients for minimizing nondifferentiable functions. Math Program 7(1):380–383. https://doi.org/10.1007/BF01585533Zhang 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.018Zhao 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:102264672520