(626a) A Network-Sampling Algorithm for the Solution of Large-Scale Supply Chain Models

The rapid evolution of production systems and the globalization of markets is driving the development of large-scale supply chain network models and algorithms [1]. In spite of developments in computational power and algorithmic sophistication, supply chains have grown to the point where they are still challenging to solve in their entirety [2]. This growth has been the driving force behind decomposition algorithms which take advantage of the underlying disconnected nature of supply chain problems to make gains in solution times [3]. Well-known decomposition algorithms include the Lagrangian decomposition [4,5,6,7], bilevel decomposition [8,9], and the Benders decomposition [10]. Lagrangian decomposition has been the focus of particular research, with algorithms able to solve large programs to 3-5% optimality gap in competitive time [4,5]. The logical premise shared by decomposition algorithms is the identification of some substructure within a problem by which it can be decomposed into subproblems; for sufficiently hard problems it is computationally cheaper to solve the set of subproblems than the original. Building on this concept, we propose a solution algorithm for large scale supply chain problems based on randomized sampling.

A connected supply chain network with n nodes grows in complexity on O(n²) due to the number of edges. This quadratic growth limits off-the-shelf solvers at large scales. One approach to resolving this complexity is to use a random sampling paradigm, which generates a low-complexity supply chain problem by sampling a small set of edges from the entire edge set. This "network-sampling" approach thus solves a low-complexity sample problem to produce a suboptimal (but feasible) solution and provides a lower bound (for a maximization problem). To determine the degree of optimality, we apply a constraint aggregation approach to relax the feasible region and derive an upper bound producing an estimate of the optimality gap. This approach thus generates a lower and upper bound that allows us to determine the degree of sub-optimality of the sample approximation and to tune the number of edges needed in the approximation. This bounding approach resembles that used in the solution of stochastic programs [11].

We apply our algorithm to a large-scale agricultural waste management market coordination problem [12]. This problem explores a dairy waste supply chain operating under a market coordination system that maximizes social welfare (the total profit of all supply chain stakeholders, subject to conditions guaranteeing that no stakeholder is allocated a loss). This model has 1,372 nodes, 1.8 million edges, 12 product processing technologies, and 20 products. The problem is intractable with conventional solvers such as Gurobi. Using our network sampling approach, we can find an approximate solution with and optimality gap of 0.3% in 21 minutes. We attribute the he ability to obtain small gaps to the inherent degeneracy (solution multiplicity) found in many large-scale supply chain models. These results are promising and suggest that our approach can be useful in solving other types of supply chain formulations.

References:

[1] Villa, Agostino. "Emerging trends in large-scale supply chain management." International Journal of Production Research 40.15 (2002): 3487-3498.

[2] Garcia, Daniel J., and Fengqi You. "Supply chain design and optimization: Challenges and opportunities." Computers & Chemical Engineering 81 (2015): 153-170.

[3] Grossmann, Ignacio E. "Advances in mathematical programming models for enterprise-wide optimization." Computers & Chemical Engineering 47 (2012): 2-18.

[4] Jackson, Jennifer R., and Ignacio E. Grossmann. "Temporal decomposition scheme for nonlinear multisite production planning and distribution models." Industrial & engineering chemistry research 42.13 (2003): 3045-3055.

[5] Sousa, R. T., Liu, S., Papageorgiou, L. G., & Shah, N. (2011). Global supply chain planning for pharmaceuticals. Chemical engineering research and design, 89(11), 2396-2409.

[6] You, Fengqi, and Ignacio E. Grossmann. "Mixed-integer nonlinear programming models and algorithms for large-scale supply chain design with stochastic inventory management." Industrial & Engineering Chemistry Research 47.20 (2008): 7802-7817.

[7] 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.

[8] Bok, J. K., Grossmann, I. E., & Park, S. (2000). Supply chain optimization in continuous flexible process networks. Industrial & Engineering Chemistry Research, 39(5), 1279-1290.

[9] Iyer, Ramaswamy R., and Ignacio E. Grossmann. "A bilevel decomposition algorithm for long-range planning of process networks." Industrial & Engineering Chemistry Research 37, no. 2 (1998): 474-481.

[10] You, F., & Grossmann, I. E. (2013). Multicut Benders decomposition algorithm for process supply chain planning under uncertainty. Annals of Operations Research, 210(1), 191-211.

[11] Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502

[12] Sampat, Apoorva M., Yicheng Hu, Mahmoud Sharara, Horacio Aguirre-Villegas, Gerardo Ruiz-Mercado, Rebecca A. Larson, and Victor M. Zavala. "Coordinated management of organic waste and derived products." Computers & chemical engineering 128 (2019): 352-363.