Product decomposition strategy for optimization of supply chain planning

Abstract

Optimization of large-scale supply chain planning models requires the application of decomposition strategies to reduce the computational expense. Two major options are to use either spatial or temporal Lagrangean decomposition. In this paper, to further reduce the computational expense a novel decomposition scheme by products is presented. The decomposition is based on a reformulation of knapsack constraints in the problem. The new approach allows for simultaneous decomposition by products and by time periods, enabling the generation of a large number of subproblems, that can be solved by using parallel computing. The case study shows that the proposed product decomposition exhibits similar performance as the temporal decomposition, and that selecting different orders of products and aggregating the linking constraints can improve the efficiency of the algorithm.

Keywords

supply chain planning / Lagrangean decomposition / mixed-integer programming

References

[1] Alvarez J, Redondo J, Camponogara E, Normey-Rico J, Berenguel M, Ortigosa P (2013). Optimizing building comfort temperature regulation via model predictive control. Energy and Building, 57: 361–372

[2] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2010). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1): 1–122

[3] Calfa B A, Agarwal A, Grossmann I E, Wassick J M (2013). Hybrid Bilevel-Lagrangean decomposition scheme for the integration of planning and scheduling of a network of batch plants. Industrial & Engineering Chemistry Research, 52(5): 2152–2167

[4] Chen B, Guignard M (1998). Polyhedral analysis and decompositions for capacitated plant locationtype problems. Discrete Applied Mathematics, 82(1–3): 79–91

[5] Dunning I, Huchette J, Lubin M (2017). JuMP: A modeling language for mathematical optimization. SIAM Review, 59(2): 295–320

[6] Erlenkotter D (1978). A dual-based procedure for uncapacitated facility location. Operations Research, 26(6): 992–1009

[7] Fisher M L (1985). An applications oriented guide to Lagrangian relaxation. Interfaces, 15(2): 10–21

[8] Geoffrion A M (1974). Lagrangean relaxation for integer programming. In: Balinski M, eds. Mathematical Programming Studies. Berlin: Springer

[9] Granada M, Rider M J, Mantovani J, Shahidehpour M (2012). A decentralized approach for optimal reactive power dispatch using a Lagrangian decomposition method. Electric Power Systems Research, 89: 148–156

[10] Graves S C (1982). Using Lagrangean techniques to solve hierarchical production planning problems. Management Science, 28(3): 260–275

[11] Guignard M (2003). Lagrangean relaxation. Top (Madrid), 11(2): 151–200

[12] Guignard M, Kim S (1987). Lagrangean decomposition: A model yielding stronger Lagrangean bounds. Mathematical Programming, 39(2): 215–228

[13] Gupta A, Maranas C D (1999). A hierarchical Lagrangean relaxation procedure for solving midterm planning problems. Industrial & Engineering Chemistry Research, 38(5): 1937–1947

[14] Gurobi Optimization (2015). Gurobi optimizer reference manual.http://www. gurobi. com

[15] Held M, Karp R M (1970). The traveling-salesman problem and minimum spanning trees. Operations Research, 18(6): 1138–1162

[16] Jackson J R, Grossmann I E (2003). Temporal decomposition scheme for nonlinear multisite production planning and distribution models. Industrial & Engineering Chemistry Research, 42(13): 3045–3055

[17] Kearney A T (2004). The complexity challenge: A survey on complexity management across the supply chain. AT Kearney Publications,https://www.atkearney.de/content/misc/wrapper.php/id/49230/name/pdf complexity management s 1096541460ee67. pdf

[18] Kelley J E Jr (1960). The cutting-plane method for solving convex programs. Journal of the Society for Industrial and Applied Mathematics, 8(4): 703–712

[19] Kelly J D, Zyngier D (2008). Hierarchical decomposition heuristic for scheduling: Coordinated reasoning for decentralized and distributed decision-making problems. Computers & Chemical Engineering, 32(11): 2684–2705

[20] Lemarechal C, Strodiot J J, Bihain A (1981). On a bundle algorithm for nonsmooth optimization. In: Managasarian O L, Meyer R R, Robinson S M, eds. Nonlinear programming 4. New York: Academic Press

[21] Mouret S, Grossmann I E, Pestiaux P (2011). A new Lagrangian decomposition approach applied to the integration of refinery planning and crude-oil scheduling. Computers & Chemical Engineering, 35(12): 2750–2766

[22] Oliveira F, Gupta V, Hamacher S, Grossmann I E (2013). A Lagrangean decomposition approach for oil supply chain investment planning under uncertainty with risk considerations. Computers & Chemical Engineering, 50: 184–195

[23] Terrazas-Moreno S, Trotter P A, Grossmann I E (2011). Temporal and spatial Lagrangean decompositions in multi-site, multi-period production planning problems with sequence-dependent changeovers. Computers & Chemical Engineering, 35(12): 2913–2928

[24] van Elzakker M, Zondervan E, Raikar N, Hoogland H, Grossmann I E (2014). An SKU decomposition algorithm for the tactical planning in the FMCG industry. Computers & Chemical Engineering, 62: 80–95

[25] Wang S H (2003). An improved stepsize of the subgradient algorithm for solving the Lagrangian relaxation problem. Computers & Electrical Engineering, 29(1): 245–249

[26] Wu D, Ierapetritou M (2006). Lagrangean decomposition using an improved Nelder–Mead approach for lagrangean multiplier update. Computers & Chemical Engineering, 30(5): 778–789

[27] Rodriguez M A, Harjunkoski I, Grossmann I E (2014). Optimal supply chain design and management over a multi-period horizon under demand uncertainty. Part II: A Lagrangean decomposition algorithm. Computers & Chemical Engineering, 62: 211–224

Acknowledgments

The authors acknowledge the financial support from the Center for Advanced Process Decision-making (CAPD) from Carnegie Mellon University, and the Government of Chile through its Becas Chile program.

RIGHTS & PERMISSIONS

2018 The Author(s) 2018. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)