# A Smoothing SAA Method for Solving a Nonconvex Multisource Supply Chain Stochastic Optimization Model

Authors: Chunlin Deng; Yao Xiong; Liu Yang; Yi Yang
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

We construct a new multisource supply chain stochastic optimization model when the supply and demand are both uncertain. This model is nonconvex because the decision variables are truncated by the random variable in the objective function. It is a common technical challenge encountered in many operations management models. To address this challenge, we adopt a novel transformation technique to transform the nonconvex problem into an equivalent convex optimization problem. Then, we provide a smoothing sample average approximation (SAA) method to solve the transformed problem. The SAA model is a good approximation for the expected value function in the objective function when the number of samples is large enough. The smoothing technique can transfer the nonsmooth plus function into a smoothing function in the model, and thus, we can use the numerical methods for the common nonlinear integer programming to solve the transformed model. Numerical tests verify the effectiveness of the new model and the smoothing SAA method.


---

## Body

## 1. Introduction

In the upstream structure of a multisupplier-single-factory supply chain, multisource decision-making is considered in the environment of uncertain demand and supply. In order to deal with the risk of these supply uncertainties, most companies adopt multiple supply source strategies, i e., when there is only one major partner supplier; in order to reduce the risk of supply uncertainty caused by emergencies, most enterprises will choose another supply source as a backup supplier [1–5]. For example, in the aforementioned Philips interruption of the provision of radio frequency chip events, Nokia’s backup quickly responded and quickly put into production, but Ericsson eventually exited the mobile phone business market because of the lack of backup suppliers.The multisource supply chain stochastic optimization model was first studied by Barankin [6] in the one-period setting and then extended by Daniel [7], Fukuda [8], and Whittmore and Saunders [9] to the various settings, see [6–9]. In 2012, Feng and Shi considered a joint inventory control and pricing problem with multiple suppliers whose supply capacities are uncertain [10]. They show that, with deterministic capacities, ordering from a cheaper source first is optimal. However, when the supply capacities are random, such a policy is not optimal. They show that the optimal policy can be characterized by a near reorder point. In 2014, Zhou and Chao [11] provide a dual-sourcing problem with price sensitive demand and a regular supplier; they characterize the structure of the optimal policy of the dual-sourcing problem. Then, Gong et al. [12] generalized the structural analysis to a dual-sourcing problem with price sensitive demand and Markovian supply interruptions. In all these models, there are no capacity limits on the supplies. To the best of our knowledge, most current research work simply assumed that supply accounts for a certain proportion of orders, ignoring supply uncertainties, i.e., uncertainties arising from unreliable product supply processing processes, such as suppliers delivering only part of the product or canceling orders [1–12]. Each potential supplier corresponded to a random supply and a unit ordering cost, the enterprise must make a decision on the quantity ordered by each supplier before the demand and supply was realized, so the final volume of transportation was the minimum between supply and order quantity. So, in this paper, we introduce the decision variable truncated by random variables and construct a multisource supply chain optimization model which is more in line with the actual construction of the supply uncertainty environment. Because the random variable truncation destroys the convexity of the problem, it is very challenging to solve and analyze this kind of nonconvex optimization problem. Based on the work of [4, 5], we first transform this problem into an equivalent convex minimum problem and then give a smoothing SAA algorithm to solve the problem. Finally, the validity of the model and algorithm is verified by numerical examples.The structure of this paper is as follows. In Section2, we establish a stochastic optimization model for the multisource supply chain problem with decision variables truncated by random variables. In Section 3, a novel transformation technique is used to transform the nonconvex multisource supply chain optimization model into an equivalent convex optimization model. In Section 4, for the solution of the transformed model, the expected value function is firstly treated with the sample average approximation method, and then, a smoothing algorithm is provided to deal with the nonsmoothness in the model. In Section 5, we provide a numerical test for a specific dual-source supply chain problem and analyze the impact of the ordering cost, supply capacity, and other factors on the enterprise’s ordering strategy. The conclusion of this paper is given in Section 6.


## 2. Establishment of the Model

We consider a single cycle and single product supply chain with multiple suppliersN=1,…,n in uncertain demand and supply environment. It is assumed that there is no fixed cost, and the quantity supplied by supplier j∈N is Kj. Here, we assume that the sequence Kj,j∈N, is independent of each other, and they are random variables of the same distribution. Demand d is also random, and the random distribution of supply quantity Kj is independent of each other. The unit ordering cost at the supplier is cj; without loss of generality, we assume that c1≤c2≤⋯≤cn. The event is divided into two phases: the ordering phase and the selling phase. In the ordering stage, the enterprise first reviews the existing inventory level and the unprocessed orders and sets the order before observing the supplier’s supply quantity Kj. Let qj represent the ordering quantity at supplier j∈N, and we use kj to represent the realized supply quantity of Kj. Then, the actual supply obtained by the enterprise is qj∧kj, where ⋅∧⋅=min⋅,⋅ is the minimum component symbol (see the same definition in [4]). Noting that the supply uncertainty of the supplier has been solved at this time, the same settings were set in the study on the stochastic production problem in [13] because the supply uncertainty at this time is mainly due to the unreliable production process and production time. In the selling phase, the requirements are realized, the remaining products are processed, and the unmet requirements are backlogged. The unit shortage cost and the unit residual value are h− and h+, respectively. Let p represent the unit retail price of the product. The enterprise’s goal is to develop a multisource ordering strategy to minimize the total expected cost. Based on random variable truncation, we establish the following unconstrained multisource supply chain optimization model:(1)minEfq∧k=E∑j∈Ncjqj∧kj+h−d−∑j∈Nqj∧kj+−pd−d−∑j∈Nqj∧kj+−h+∑j∈Nqj∧kj−d+,where x+=maxx,0,f:ℱn⟶ℝ¯ is the function of the decision variable qj, here ℱ is either the real space or the space with integers Z and ℝ¯=ℝ∪+∞, kj,d are random variables, and the support sets of the random vectors k=k1,k2,…,kn and d=d1,d2,…,dn are Suppk=X⊂ℱn and Suppd=Y⊂ℱ, respectively.In model (1), the first and second items in the objective function represent the total order cost and the total shortage cost, respectively, and the third and fourth items represent the total profit on the sale and the residual value, respectively. As a matter of convenience, model (1) can be arranged as follows:(2)minEfq∧k=E∑j∈Ncjqj∧kj+h−+pd−∑j∈Nqj∧kj+−h+∑j∈Nqj∧kj−d+−pd.


## 3. Equivalent Transformation Technique

In general, even iff is convex, problem (2) is a nonconvex optimization problem due to the existence of truncated item qj∧kj. As Ciarallo et al. pointed out in [14], for the production planning problem of single product and single cycle supply chain with uncertain supply and demand, random supply will lead to the generation of a single peak and nonconvex objective function, and they also verified that the objective expectation function has quasi-convexity.Recently, Chen Xin et al. [4, 5] proposed an effective conversion technique to transform a nonconvex minimization problem into a convex minimization problem and further showed that this method could maintain some good structural properties, such as convexity, submodality, and L♮− convexity. Therefore, based on the result in [4, 5], we get the following theorem for problem (1).Theorem 1.
Assume that (a) functionf:ℱn⟶ℜ¯ is a lower semicontinuous function and satisfies fx⟶∞, |x|⟶∞; (b) f is the component convex function (if ℱ=Z, f is the component discrete convex function); (c) the components of the random vector k are independent of each other, and the corresponding realization is kj∈X=Suppk. Let ϑ∗ represent the optimal value of model (2); then, ϑ∗ is also the optimal objective value of the following optimization model:(3)min,Efυk=E∑j∈Ncj⋅υjkj+h−+pd−∑j∈Nυjkj+−h+∑j∈Nυjkj−d+−pd,s.t.,υjkj=qj∧kj,υk=υ1k1,…,υnkn.Proof.
Letσ∗ be the optimal target value of model (3), since, for any q∈ℱn, the equality constraint υjkj=qj∧kj is feasible in model (3), so we get σ∗≤ϑ∗.
Next, we just need to prove thatϑ∗≤σ∗. Obviously, the conclusion is right when σ∗=∞, so in the following analysis, we firstly assume σ∗<∞; then, combining condition (a), we can know that models (2) and (3) both have finite optimal solutions. In the following, we can prove that given any optimal solution υ∗=υkj|kj∈X, we can find a solution q^∈ℱn that satisfies Efq^∧k=Efυ∗k by mathematical induction.
Whenn=1, let q^=argminq∈ℱnfq (take the minimum value if there are multiple optimal solutions), and for any feasible solution of model (3), according to Lemma 3.1 in [4], we have fq^∧kj≤fυkj, for ∀kj∈X, so we get Efq^∧k≤σ∗. Note that q^ is a feasible solution of model (2), which means that ϑ∗=Efq^∧k≤σ∗; combined with σ∗≤ϑ∗, we get σ∗=ϑ∗.
Whenn>1, let qj∗,j=1,…,n, be the jth element of q∗; starting with the first element, we define(4)σ1q1=Efq1,υ2∗k2,…,υn∗kn.
In condition (b), the component convexity off means that σ1q1 is convexity on q1. Since all components of the vector k obey a relatively independent and identical distribution, Ek1σ1υ1∗k1=Ek1fυ1k1,υ2∗k2,…,υn∗kn) is valid for any measurable function υ1k1, and based on the previous analysis of case n=1, we have that there is a q^1, which satisfies the following equation:(5)σ∗=minEσ1υ1k1|υ1k1≤k1,∀k1∈X1,υ1k1∈ℱ=minq1∈ℱEσ1q1∧k1=Eσ1q^1∧k1.
Then, we go on to defineσ2q2=Efq^1∧k1,q2,υ3∗k3,…,υn∗kn, and obviously, σ2 is also convex; similarly, there is q^2 that satisfies the following equation:(6)σ∗=minEσ2υ2k2|υ2k2≤k2,∀k2∈X2,υ2k2∈ℱ=minq2∈ℱEσ2q2∧k2=Eσ2q^2∧k2.
Repeat the above steps, and defineσiqi=Efq^1∧k1,…,q^i−1∧ki−1,qi,υi+1∗ki+1,…,υn∗kn. In the same way, we can find q^i,i=3,…,n, which satisfies the following equations:(7)σ∗=minEσiυiki|υiki≤ki,∀ki∈Xi,υiki∈ℱ=minqi∈ℱEσiqi∧ki=Eσiq^i∧ki.
So,(8)σ∗=Eσnq^n∧kn=Efq^1∧k1,…,q^n∧kn.
Sinceq^ is a feasible solution of model (3), we know that ϑ∗≤Efq^∧k=σ∗; combined with σ∗≤ϑ∗, we get σ∗=ϑ∗.
Based on the above theorem, we successfully transformed the nonconvex supply chain optimization model (2) into an equivalent convex supply chain optimization model (3), see [4, 5].


## 4. Solution Method of Model (3)

To solve model (3), we firstly use the SAA method to approximate the expected value function in the objective function. It is well known that Shapiro have proved that, under some regularization conditions, the optimal value of SAA problem converges to the optimal value of the original stochastic programming problem according to probability 1 as the number of samples approaches infinity (Chapter 6 of [15]). Assume that kjm,m=1,…,M, and dl,l=1,…,L, are the random samples generated by supply kj,j=1,…,n, and demand d, respectively; then, the SAA model for multisource supply chain problems is(9)min1M∑m=1M∑j∈Ncj⋅υjkjm+1ML∑m=1M∑l=1Lh−+p⋅dl−∑j∈Nυjkjm+−1ML∑m=1M∑l=1Lh+⋅∑j∈Nυjkjm−dl+−1L∑l=1Lp⋅dlυjkjm≤kjm,j=1,…,n,υkms.t.=υ1k1m,…,υnknm.Obviously, there is a nonsmooth plus function⋅+ in model (9) which will cause difficulty in computing this problem. So, we use a smoothing approach in [16–19] to deal with nonsmoothness in multisource supply chain problems. For the sake of simplicity, we denote(10)Gυk=1M∑m=1M∑j∈Ncj⋅υjkjm+1ML∑m=1M∑l=1Lh−+p⋅dl−∑j∈Nυjkjm+−1ML∑m=1M∑l=1Lh+⋅∑j∈Nυjkjm−dl+−1L∑l=1Lp⋅dl.Lett>0 be a smooth parameter; we construct the following smoothing approximation functions by using the same technique in [14]:(11)gtt,υk=tln1+expdl−∑j∈Nυjkjmt,htt,υk=tln1+expdl−∑j∈Nυjkjm−dlt,G¯t,υk,=1M∑m=1M∑j∈Ncj⋅υjkjm+1ML∑m=1M∑l=1Lh−+p⋅gtt,υk−1ML∑m=1M∑l=1Lh+⋅htt,υk−1L∑l=1Lp⋅dl,where gtt,υk, htt,υk, and G¯t,υk are the smooth approximation functions of gυk,hυk,Gυk, respectively. We can prove that the smooth functions have the following properties.Theorem 1.
For∀t>0, we can obtain(i)
G¯t,υk is an increasing function of t, and we have(12)G¯t,υk−Gυk≤tlnt.(ii)
Gυk is a convex function of υk, and G¯t,υk remains convex of Gυk.(iii)
G¯t,υk is a continuous differentiable function whose first derivative is(13)∇υkG¯t,υk=1ML∑m=1M∑l=1Lh−+p⋅expdl−∑j∈Nυjkjm/t1+expdl−∑j∈Nυjkjm/t−h+⋅expdl−∑j∈Nυjkjm−dl/t1+exp∑j∈Nυjkjm−dl/t+∑j∈Ncj.iv For any fixed υk∈ℜN×M, there is(14)∇υkG¯t,υk−∂Gυk=ot.Proof.
According to Lemma 3.1 in [16], conclusion i, iii, and iv are obviously valid. For conclusion ii, since G¯t,υk is the sum function of linear functions gtt,υk, htt,υk, and gtt,υk and htt,υk are convex functions and the sum function of convex functions remains convex, conclusion ii is valid.
According to Theorem1, we know that the smooth functions gtt,υk, htt,υk, and G¯t,υk are all convex functions, and when the smooth factor t⟶0+, the smooth functions have a good approximation effect. Therefore, we can construct the following smoothing model of multisource supply chain to solve model (2):(15)minG¯t,υks.t.υjkjm≤kjm,j=1,…,n,υkm=υ1k1m,…,υnknm.
Model (15) is a smooth nonlinear convex programming problem with dimension n×M (n is the number of suppliers).


## 5. Numerical Tests

In this section, we give numerical tests for the new model (1) and the smoothing SAA method. The computation is performed in MATLAB R2021b, in a computer with CPU Apple M1 and RAM 16 GB.Consider a double source supply chain problems when supply and demand are both uncertain. The experimental data are from [1] in which the enterprise has two suppliers: the unit ordering costs of each supplier are c1 and c2, respectively; the unit shortage cost and the rest of the residual value are h− and h+, respectively; the retail price of unit product is p. Assume that the market demand of the product d is uniformly distributed on a,b. In order to describe the positive dependence between random supplies, we consider the case where suppliers share a “market risk.” For example, in reality, suppliers suddenly receive urgent orders from enterprises, and the supply of each supplier j is set as kj=yj+z, j∈N, where yj and z are mutually independent random variables subject to uniform distribution, the market risk factor z obeys the uniform distribution on c,d and is embedded into the supply provided by each supplier, and yj obeys the uniform distribution on ej,fj.Set the number of samplesM=L=100, the smooth parameter t=0.001, and the basic parameters are set as c1=50, c2=80, h−=30, h+=20, p=100, a=5000, b=10000, c=2500, and d=5000, when the supply capacity of the two suppliers is the same, that is, e1=e2=2500 and f1=f2=5000. Based on the above initial number, we solve the smoothing model (15) and get the optimal ordering strategy q∗=7643,2188T, and the expected profit is −E⋅=419300. The results show that when the supply capacity of the cooperative suppliers is the same, the enterprise gives priority to place orders to supplier 1, that is, the enterprise chooses the supply source based on the ordering cost, which is consistent with the data results in [1].Then, we consider the influence of smooth parametert in the algorithm. Set the number of samples M=L=100; the results are shown in Figure 1. It can be seen that the optimal target value does not change significantly. This indicates that the smoothing algorithm is not sensitive to the parameter t and further indicates that the original model is equivalent to the smoothing model when t⟶0+.Figure 1
The effect of the smoothing parameter on the object function.In the following, we consider the influence of supply capacity on decision-making. Let the sample sizeM=L=100 and smooth parameter t=0.001; the results are given in Table 1 and Table 2.Table 1
The influence of supply capacity on enterprise decision-making wheny1∼U2500,5000andy2∼U0,2000.
e125002500250025002500f150005000500050005000e202000400060008000f2200040006000800010 000q1∗77057531757675107531q2∗19202354222823532354−E⋅416 850417 160413 940416 000417 160CPUs5.486 9785.609 1305.564 0755.536 3815.552 392Table 2
The influence of supply capacity on enterprise decision-making wheny1∼U1000,5000 and y2∼U5000,9000
e101000200030004000f110002000300040005000e250004000300020001000f290008000700060005000q1∗14712476398355097244q2∗84477547607545462779−E⋅234 930265 720310 190356 860404 470CPUs4.805 8594.770 5694.796 6334.816 0094.751 742From Table1 and Table 2, we can see that the optimal order quantity of an enterprise is determined by the wholesale price and supply capacity of the supplier. As we can see in Table 1, in the case of c1<c2, when the supply capacity of the fixed supplier 1 is y1∼U2500,5000, no matter how good or bad the supply capacity of supplier 2 is, the enterprise will choose to place an order with supplier 1 firstly; this may be due to the high supply capacity of supplier 1, and it can make the market demand reach the saturation state, so the enterprise will tend to choose the supplier with the lower order cost. From Table 2, we can see that, although c1<c2, the optimal ordering strategy is q2∗>q1∗ when the supply capacity of supplier 1 is much lower than that of supplier 2. Of course, when the supply capacity of supplier 1 increases, so does its order quantity q1∗. This indicates that when the market demand does not reach the saturation state, the ordering decision q∗ of the enterprise is influenced by the ordering cost cj and supply capacity kj of the supplier. Moreover, it seems that, in order to meet the demand of the market, the enterprise will even ignore the loss caused by higher costs and choose suppliers with higher supply capacity.


## 6. Summary

In this paper, we establish a multisource supply chain optimization model with random variable truncation to deal with the uncertainty of the supply and demand. By introducing a new variable, we transfer the nonconvex multisource supply chain model into a convex problem; then, we provide a smoothing SAA algorithm to solve the equivalent problem. The equivalence of the transformed models and the convergence properties of the smoothing approximation function are also given, and numerical tests show that (i) the smoothing SAA method can solve the multisource supply chain optimization model efficiently, (ii) when the supply capacity of the supplier is consistent, the enterprise will choose the supply source based on the ordering cost of the supplier, and (iii) the ordering decision of enterprises is influenced by both ordering cost and supply capacity. In other words, when the supply capacity of suppliers with low ordering cost is large enough to make the market demand reach saturation state, enterprises tend to choose suppliers with low ordering cost. When the supply capacity of suppliers with lower ordering costs cannot meet the market demand, enterprises tend to trust suppliers with higher supply capacity.



---

*Source: 5617213-2022-02-22.xml*