1. INTRODUCTION
Recently, industrial environment has been encountering a period of extension and globalization in which the organizations capacity turns into a basic achievement factor in the focused market for reacting to variable and progressively advanced client requests (Elsaghier, 2017). Supply chain management is a marvel that shaped to react clients request in solid and speedy administration condition with superb items at the base cost. A standout among the most essential key level choices in the supply chain management field is supply chain network plan that assumes a noteworthy part in the general execution of the Supply chain. By and large, supply chain network organizing plan choices incorporate deciding the number, location, capacity and the innovation of the required system offices and the total amounts of stream between them to precisely consider their demand (Christopher, 2016).
The oil industry is engaged with a worldwide supply chain that incorporates residential and global transportation, requesting and stock perceivability and control, materials considering, import/export help and data innovation. In this way, the industry offers an exemplary model for executing supply chain management procedures. In the oil industry, all huge and vital tasks are arranged ahead of time. Along these lines, the entire procedure can be kneaded and adjusted into an elite cash making machine. The purpose of supply chain network management is to give the most extreme client benefit at the very least conceivable cost.
In the business supply chain interface, investigation tasks make an incentive through seismic examination and recognition of prospects. Creating activities turns into the clients that utilize the yield of the investigation.
There is a need to guarantee that each organization or administrator along with the supply chain network can react rapidly to the correct material needs of its clients, shield itself from issues with providers and cushion its tasks from the request and supply vulnerability it faces. For oil organizations, the overall revenue can be enormously upgraded if the organizations deal with their purchase of dollars all through the whole supply chain.
One of the shortcomings of a supply chain is that each organization is probably going to act on its greatest advantage to streamline its benefit. The objective of fulfilling a definitive client is effortlessly lost and openings that could emerge from some coordination of choices crosswise over phases of the store network could likewise be lost. In the event that suppliers could be more expert, there would be less requirement for inventories of crude materials, quality examination frameworks, bringing about lean generation. The utilization of optimization methods for supply chain outline and arrangement has been accounted for in the writing since the Melo et al. (2009) showed a broad writing survey on store network models. In spite of the fact that the exploration writing on the vital display of supply chains is very rich, just a small number of the examinations have unequivocally included vulnerability in the definition. As indicated by Sahinidis (Sahinidis, 2004), the fuse of vulnerability into arranging models utilizing stochastic improvement remains a test because the substantial computational prerequisites are included.
In order to deal with this issue, a few specialists have proposed approaches that are fit for stochastic integer programming problems. These methodologies either endeavor to adjust the LShaped calculation into the setting of stochastic integer programming problems using convexification procedures for the secondstage issue (see, for instance Laporte and Louveaux, 1993;Sherali and Fraticelli, 2002;Zheng et al., 2013), enumerative branchand bound procedures (see for instance Carøe and Schultz, 1999;Norkin et al., 1998), or apply double disintegration strategies by methods for Lagrangian relaxation and Benders decomposition approaches (Carøe and Schultz, 1999). The Lagrangian relaxation procedure uses the idea of relaxing the explicit linear constraints by bringing them into the objective function with associated vector μ called the Lagrange multiplier. A few techniques have been proposed in the writing for taking care of the double issue relative to the Lagrangian relaxation. The accessible procedures incorporate the established subgradient technique (Held and Karp, 1971;Held and Wolfe, 1974), cutting plane approaches (Kelley, 1960;Redondo and Conejo, 1999), the volume algorithm (Barahona and Anbil, 2000), bundle methods (Lemaréchal, 1989;Zhao and Luh, 2002), and augmented Lagrangian relaxation methods (Ruszczynski, 1995;Li and Ierapetritou, 2012).
Benders decomposition method (Benders, 1962) is one of the most important and effective methods for solving the mixed integer programming problems and has been applied in various fields such as network, transportation, supply chain, scheduling etc. In this method by omitting the complicated variables, the primary problem transforms into a subproblem and a master problem which by minimizing the problem it creates an upper bound subproblem and a lower bound master problem for obtaining an optimal solution. In Benders algorithm iteration, dual subproblem objective function, by means of the master problem optimal solution from the previous iteration is updated and in any iterations, the feasibility and optimality cuts are added to the master problem. These cuts from extreme points (extreme rays) give the space of dual subproblem solution. The main idea of Benders decomposition method is on the basis that prior to use all the cuts, the conditions of optimality and feasibility and convergence must be established.
The cross decomposition methods benefits simultaneously from the upsides of Lagrangian relaxation and Benders decomposition approaches. In this algorithm each subproblem is a passage for other master problem. As it is the master problem of any strategy is fortified with the acquired data out of subproblems.
The cross decomposition methods, first proposed by Van Roy (1983) alongside the meeting testing for evasion of taking care of master problems (the less demanding fathoming with the guide of subproblems) that contrasted and the accessible techniques created a diminishment in estimate of 20 percent in the season of critical thinking. Holmberg (1990) examined a wide range of this technique of convergence testing and proposed the normal estimation of the cross decomposition strategy for the utilization of finish exclusion of the master problem through utilizing cycle of the past arrangements. As to the headway of MIP solvers, more catalyst PCs, as well as the parallel issue arrangement, Mitra et al. (2016) proposed the utilization of tackling the master problem and the exclusion of convergence test. In this paper we display a far reaching structure for the multiproduct, multiperiod supply chain investment planning considering system plan and discrete limit development under demand uncertainty.
The content of this article is organized as follows. Background of the problem considering this paper presented in Section 2. Section 3 describes the problem statement, while Section 4 presents the mathematical model formulation. We briefly explain each of the exact methods of Benders decomposition and Lagrange relaxation for solving the mixed integer programming problems and we present a new hybrid Lagrangian relaxation algorithm for updating the Lagrangian multiplier set, based on the combination of cuttingplane, subgradient and trustregion strategies. Then we submit the proposed algorithm for the new cross decomposition method by combination of Benders decomposition and hybrid Lagrangian relaxation methods in section 5. Numerical results from an example case and for a real world case study problem are presented in Section 6. Finally, we draw some conclusions in Section 7.
2. BACKGROUND
The problem approached in this paper can be defined as the strategic planning of petroleum products distribution, where one tries to choose investments to be made in coordination’s framework, mulling over choices with respect to the appropriation of streams, stock strategies, and the level of the outer commercialization of refined items. Such choices emerge with regard to the key and strategic arrangement looked at by oil based commodities appropriation organizations working over extensive geological areas. We consider this issue as an incorporated conveyance, organizing plan and binary capacity extension problem under a multiproduct and multiperiod setting.
Petroleum products commodities from refineries are put away in tanks to be coordinated to distribution bases. These bases fill in as arrangement focuses with merchants and are considered as accumulation purposes of interest for such products. They additionally may fill in as a middle point for different bases advance far from the refineries. The bases are equipped for putting away item when vital, given that the issue is considered under a multiperiod activity. The capacity and throughput limits of the bases are constrained. Be that as it may, they can be enhanced through a development venture. A similar thought holds for curves, which can likewise be extended in a similar manner. Notwithstanding, we additionally think about building new circular segments and bases. The tanks of these bases are continually being stacked and emptied. This procedure is known as the tank pivot and is liable to the physical constraints that are inalienable in the equipment related to the tanks of the circulation base. The pivoting capacity alludes to the circumstances a tank can be filled with and exhausted over a certain period of time.
Since we are managing uncertainty of the demand levels, the facts might confirm that the base does not have enough tankage available to deal with unexpectedly high demand. At the point when this is the situation, transportation boats can be utilized as impermanent tanks in places where marine access is accessible. This is just done under critical conditions because of the high effect on the logistic costs.
3. PROBLEM STATEMENT
Considering an arrangement of items that are provided from a few multiproduct creation locales and transported to an arrangement of bases that can be either a middle point, a demand point, or both. Transportation is performed through capacitated circular segments and is in this way, subject to capacity accessibility constraints. Let Ρ be the set of the products, S the set of suppliers and B the arrangement of bases considered. Figure 1 represents a small example of the system structure and the kind of investment decisions to be taken. In order to delineate this, we think about one supply node (S = {S1}) and three bases (B = {B1, B2, B3})  four after N periods, accepting the portrayal of the choice of making B4, i.e., B = B∪{B4}) One may see that the structure changes along the time horizon, as is exemplified by the extension of B1, and the production of B4 and the circular segments that interface it to B1, B2, and B3.
The multiperiod issue is considered over a finite time horizon of size τ , where T represents the arrangement of discrete time periods that can represent months, quarters or even years. In order to demonstrate the uncertainty, we propose a twostage mixed integer linear stochastic programming model. The uncertainty is considered through the thought of Ω discrete scenarios ξ ∈ Ω. These scenarios are characterized by methods for inspecting from a persistent conveyance of the demand levels for a given product at a certain base. Additionally insights with respect to the scenario age process can be found in Oliveira and Hamacher (2012).
The firststage decisions are the determination of the development ventures for tanks and arcs, as well as their timing. These choices are represented by binary variables. Typically, these investments are exceptionally serious capital and are worked in order because of their technical complexity and specific characteristics. Consequently, we assume that the same investment can only be implemented once along the time horizon. Likewise, we expect that investment decisions are accessible for use toward the start of the appointed time period.
The secondstage decisions s are those related to the flow of products, inventory, supply levels at the sources, and the need of crisis drifting tankage. Notice that, for this situation, the secondstage decisions include both constant and binary variables. The objective function comprises investments costs of tanks and curves extension ventures and the expected costs related to freight, inventory, and emergency floating tank acquisition. The motivation behind the model is to design the transportation and inventory decisions that will adapt to the anticipated (albeit uncertain) development of product demands, together with the conceivable investment that ought to be actualized and while, minimizing both investment and expected logistic costs.
4. MATHEMATICAL MODEL
A description of the model notation is represented in Table 3 in Appendix A. The mathematical model for the optimization of the aforementioned problem can be stated as follows:
where w_{jpt} represents the capacity expansion investment decisions at location j for product p and in period t, and y_{ijt} represents the investment decisions for arcs connecting locations i and j in period t. $\phi (w,\hspace{0.33em}y)={{\rm E}}_{\text{\Omega}}\left[Q(w,\hspace{0.33em}y,\hspace{0.33em}\xi )\right]$ represents the expectation evaluated for the uncertain parameters ξ over all ξ ∈ Ω for the secondstage problem, given investment decisions (w, y). We assume in this case that the uncertain parameters are described by a discrete probability distribution function. Constraints 4.2 and 4.3 define that each investment can happen only once along the time horizon considered.
The secondstage problem $\phi (w,\hspace{0.33em}y)$ can be stated as shown in equations 4.4 to 4.10. The objective function 4.4 represents freight costs between nodes, inventory costs, and costs for hiring emergency floating capacity. Equation 4.5 comprises the material balance in distribution bases. Constraint 4.6 limits the supply availability at sources. Constraint 4.7 defines the arc capacities and the possibility of its expansion through the investment decisions. In a similar way, constraint 4.8 defines the storage capacities together with their expansion possibility and the additional emergency capacity that might be necessary. Constraint 4.9 defines minimum inventory levels, according to safety requirements. Constraint 4.10 sets the throughput limit for bases, defines by the product of the available storage capacity with the throughput capacity multiplier, and the possibility of expanding them by means of additional floating tankage.
5. SOLUTION ALGORITHM
We assume that largescale instances of the stochastic supply chain investment planning problem 4.14.3 presented in Section 4 cannot be solved in full space, and we consider that scenariocase cross decomposition is an alternative to overcome this challenge. In the following Section, we detail the algorithmic strategy for solving the mixed integer programming problem. Our method integrates a scenariocase decomposition based on a novel approach for updating the Lagrangian multiplier set and cross decomposition methods.
Supposing that we have the following mixed integer linear programming problem:
where $\text{c}\in {\text{R}}^{{\text{m}}_{\text{1}}}\text{,}\hspace{0.33em}\text{f}\in {\text{R}}^{{\text{m}}_{\text{2}}}\text{,}\hspace{0.33em}\text{b}\in {\text{R}}^{{\text{n}}_{\text{1}}}\hspace{0.33em}\text{and}\hspace{0.33em}\text{d}\in {\text{R}}^{{\text{n}}_{\text{2}}}$ and also A, B and D are matrixes ${\text{n}}_{\text{1}}{\text{\xd7m}}_{\text{1}}\text{,}\hspace{0.33em}{\text{n}}_{\text{1}}{\text{\xd7m}}_{\text{2}}\hspace{0.33em}\text{and}\hspace{0.33em}{\text{n}}_{\text{2}}{\text{\xd7m}}_{\text{2}}$ respectively. The variables of $\text{x}\in {\text{R}}^{{\text{m}}_{1}}$ are continuous and the integer and complex variables of $\text{y}\in {\text{R}}^{{\text{m}}_{2}},$, are the objective function of minimizing the total costs.
5.1 Lagrangian Relaxation Approach
One of the suitable methods for solving the problems containing complicated constraints is the Lagrangian relaxation method. The complicated constraints are those which by omitting them from the problem set, the problem turns to have a suitable and specific structure which can be utilized. The main idea of this method includes omitting the complicated constrains and adding them to the problem of objective function by using variables by the name of Lagrangian multipliers. By doing that and using duality relations, we reach a new problem which for solving it an iterative algorithm can be used. In any iteration, a new value is considered for Langrage multipliers vector and then a suitable subproblem which consists of only good constraints is solved. In this method, finding a suitable lower bound (for the problem of minimizing) depends on finding the best Lagrangian multipliers (the problem of dual Lagrange). But this method does not have any guaranteed convergence.
Regarding IP problem by omitting complicated constraint (12) and adding it to the objective function, Lagrangian subproblem is written as follows:
where λ (Lagrangian multiplier) is a real, positive and adequately large enough value. Let $\left({\tilde{x}}^{k},\hspace{0.33em}{\tilde{y}}^{k}\right)$ be the optimal solution of LSP^{k} considered. We call the above model Lagrangian subproblem. In some of the problems by considering the problem structure this subproblem can be decomposed to segregate subproblems (the method of Lagrangian relaxation).
Lemma 5.1 (Lagrangian Bounding Principle). For any Lagrangian multiplier λ, the value L_{λ} of the Lagrangian function is a lower bound on the optimal objective value z^{*} of the original problem IP.
Proof. Since Dy = d for every feasible solution y of IP, for any Lagrangian multiplier λ,
$\begin{array}{l}{\text{z}}^{*}=\text{min}\left\{{\text{c}}^{\text{T}}\text{x}+{\text{f}}^{\text{T}}\text{y}\left\text{Ax}+\text{By}=\text{b},\hspace{0.33em}\hspace{0.33em}\text{Dy}=\text{d},\hspace{0.33em}\text{x}\ge 0,\hspace{0.33em}\text{y}\ge 0,\hspace{0.33em}\hspace{0.33em}\text{integer}\right.\right\}\\ \text{}=\mathrm{min}\left\{{\text{c}}^{\text{T}}\text{x}+{\text{f}}^{\text{T}}\text{y}+\text{\lambda}(\text{Dy}\text{d})\left\text{Ax}+\text{By}=\text{b},\hspace{0.33em}\hspace{0.33em}\text{x}\ge 0,\hspace{0.33em}\hspace{0.33em}\text{y}\ge 0,\hspace{0.33em}\hspace{0.33em}\text{integer}\right.\right\}\end{array}$
Since removing the constraints Dy = d from the second formulation cannot lead to an increase in the value of the objective function (the value might decrease), ${\text{z}}^{*}\ge {\text{L}}_{\text{\lambda}}$. □
To obtain the sharpest possible lower bound, we would need to solve the following optimization problem:
Which we refer to as the Lagrangian Dual problem associated with the original optimization problem. The Lagrangian Bounding Principle has the following immediate implication.
Property 5.2 (Weak duality). The optimal solution L_{D} of the Lagrangian dual (20) is a lower bound on the value z^{*} of an optimal solution of IP, i.e. ${\text{L}}_{\text{D}}\le {\text{z}}^{*}.$
Proof. For any Lagrangian multiplier λ and for any feasible solution x of problem IP, we have ${\text{L}}_{\text{\lambda}}\le {\text{L}}_{\text{D}}\le {\text{z}}^{*}.$.□
There are different methods for solving the following problem that one classic method is subgradient method which has been proposed by Held and Karp (1971). In this method Lagrangian multipliers are usually updated as well. But for the convergence we would need a suitable strategy for defining and updating the subgradient step size. Another method, from the theoretical standpoint has better convergence properties, is the method of cutting plane which has been submitted by Cheney and Goldstein (1959). An alternative procedure for updating the Lagrangian multiplier is based on the use of cutting plans to approximate the Lagrangian dual function. This method for convergence needs many iterations. Therefore, to gain suitable Lagrangian multipliers takes a lot of time. To remove this problem, the trust region method has been proposed by Marsten et al. (1975) is used. In this method, better updating of Lagrangian multipliers can be expected while the convergence properties are established.
To update Lagrangian multipliers we use a combinational method which simultaneously applies three concepts of subgradient, cutting planes and trust region Mouret et al. (2011). The cutting planes are reliable constraints for dual problem generated in any iteration, subgradient prepares a reduction direction for dual problem, while the trust region delineates the deviation value from this direction in its range. The combination of these methods while updating the Lagrangian multipliers insures convergence.
In k+1 iteration using the following combinational dual problem, we update the Lagrangian multipliers:
where, therein υ (L_{D}) is estimated via a heuristic methods (the meaning of the sign υ is the optimal value). However, instead of heuristically updating the step size, it is optimized using variable ββ, which is bounded by the parameter β > 0. Note that the δ variable is the deviation value form the steps of subgradient and the parameter δ > 0 is the maximum deviation in directions of trust region. The parameters of β and δ, λ in any iteration are updated in heuristic methods. In practice, computational testing shows that the use of fixed values is suitable selections (Oliveria et al., 2013).
Stoppage criterion, used for this combinational strategy, is restricted based on Lagrange gap between the relaxed original problem and dual problem:
$\upsilon \left({L}_{D}{}^{k}\right)\upsilon ({L}_{\lambda}{}^{k})\le \epsilon $
It is necessary to mention that the methods of cutting planes and trust region have features of finite convergence.
5.2 Classic Benders Decomposition Method
We can rewrite this IP model as follows:
where therein is:
$\text{Y}=\left\{\left.\text{y}\right\text{Dy}=\text{d},\hspace{0.33em}\text{y}\ge 0,\hspace{0.33em}\text{integer}\right\}$
Let ${\widehat{x}}^{k}$ have the optimal solution of PSP^{k}. The inner minimization is a continuous linear problem that can be dualized by dual variables u as follows:
Let u^{k} have the optimal solution of DSP^{k}. In the Benders decomposition algorithm, we consider the relationship (26) as Benders subproblem. With regard to the duality theorem we can write the relation (25) as follows:
The feasible space of the inner maximizing problem depends on selecting y which if it is non empty for any selection of y, the problem of inner maximizing is feasible or unbounded. Therefore by adding optimal cuts (30) and feasible cuts (31), the master problem of Benders decomposition is the following (${\text{u}}_{\text{i}}^{\text{T}}$ s is the vector that corresponds to the extreme points I of the dual of PSP and ${\text{u}}_{\text{i}}^{\text{T}}$ s is the vector that corresponds to the extreme rays J of the dual of PSP):
Let y^{k} have the optimal solution of BMP^{k}. In Benders decomposition method we consider the above model as the Benders master problem. Benders decomposition algorithm due to finiteness of the extreme points (extreme rays) of dual subproblem, in the numbers of finite iteration becomes convergence. However it usually has slow convergence.
5.3 Cross Decomposition Method
One of the potential strengths of the proposed algorithm is that it guarantees to provide a lower and upper bound, which is at least as tight as the best lower bound obtained from the Lagrangian dual and best upper bound obtained from the Benders decomposition. While having a mechanism to generate firststage solutions that are feasible regarding the firststage constraints (in contrast to using a heuristic as in Lagrangian decomposition). Furthermore, we use a multicut approach for both, the primal Benders and dual Lagrangian master problem to derive primal and dual bounds. While we expect tight bounds, the computational performance needs to be carefully investigated for each case individually. We anticipate to see an impact for cases in which the Benders algorithm converges slowly due to a weak underlying linear relaxation. At the same time, the effort that an additional Lagrangian iteration adds to the total computational time needs to be compared with the number of saved Benders iterations and associated computational time.
The combination of Benders decomposition and hybrid Lagrangian relaxation methods lead to the new cross decomposition algorithm (Figure 2) in which subproblems of each of the methods are solved in parallel and these subproblems reinforce the master problems together in the form of ping pong and admit suitable upper and lower bound for the optimal solution to the original problem in any iterations.
Algorithm:

1. initialization $k=0,\hspace{0.33em}K=\left\{0\right\},\hspace{0.33em}{y}^{k=0}=0,\hspace{0.33em}{\lambda}^{k=0}=0,\hspace{0.33em}LB=\infty ,\hspace{0.33em}UB=\infty .$
Go to step 2.

2. Benders subproblem For given y^{k} solve (BSP^{k})
Store solution u^{k}, if $\upsilon (BS{P}^{k})<UB$ set $UB=\upsilon (BS{P}^{k})$ and go to step 3.

3. Lagrangian subproblem For given λ^{k} solve (LSP^{k}) in parallel
Store ${\tilde{x}}^{k},\hspace{0.33em}\hspace{0.33em}{\tilde{y}}^{k}$ and $\upsilon (LS{P}^{k})$ and go to step 4.

4. Lagrangian master problem For given ${\tilde{x}}^{k}$ and ${\tilde{y}}^{k}$ solve ($LM{P}^{k+1}$).
Store solution for Lagrangian multipliers and set ${\lambda}^{k+1}$ and update β, δ and λ and go to step 5.

5. Benders master problem For given ${u}^{k},\hspace{0.33em}\text{\hspace{0.17em}}\upsilon (LS{P}^{k})$ and k ∈ K solve ($BM{P}^{k+1}$). Store solution for ${y}^{k+1}.$.
If $LB<\upsilon (BM{P}^{k+1}),$, set $LB=\upsilon (BM{P}^{k+1})$ and go to step 6 otherwise go to step 2.

6. Check convergence(optimality) If $UBLB\le \epsilon $ stop.
Else set k= k +1 and include in K; go back to step 2.
6. ILLUSTRATIVE CASE STUDY
In order to provide some insight into the potential of the proposed algorithm, we apply the cross decomposition scheme to a Petroleum Product Supply Chain problem. Due to its large size, the problem is hard to solve with a fullspace approach (Branch and Bound method) and requires decomposition techniques to enable an efficient solution. In this section, we show the numerical results for cases where the proposed framework is applied. In GAMS 24.1.2 on the 8 processors of an Intel i7 2600 (3.40 GHZ) machine with 8 GB RAM, the fullspace model, hybrid Lagrangian relaxation algorithms (the combination of cuttingplane, subgradient and trustregion strategies) and the cross decomposition methods are achieved.
The illustration displayed in this section originates from a real world case study petroleum product supply chain under uncertainty. As for this situation we view four different products as distributed between 16 locations (13 bases, 1 refinery and 2 international suppliers). An aggregate of 28 projects for tankage extension and projects for network design were considered under a planning horizon of 5 years, isolated quarterly over 20 periods. With a specific final goal to decrease the quantity of binary variables of the model, we utilize a multiscale definition for the time horizon in regard to investment (firststage) decisions and planning (secondstage) decisions. In one sense, we total the investment decisions with the end goal that they are thought to be accessible toward the start of every semester (i.e., thinking about a semiannually partitioned horizon), while the planning choices are taken in respect to the first quarterly separated horizon. Such an approach yields an upper bounding estimation to the original problem. Every scenario relates to an arrangement of demand forecasts for each location and product. The number of scenarios to be utilized is resolved in view of a statistical method (Shapiro and Homemde Mello, (1998), to obtain solutions inside particular confidence intervals for a desired level of exactness. We utilize this method as a means of lessening the number of scenarios given that we are inspecting from a consistent restricted space. To generate scenarios and further details on the scenario generation method and definition of sample sizes for this problem, please refer to Oliveira and Hamacher (2012).
Table 1 shows the deterministic equivalent size of the problem considered for instances of different sample sizes, while Table 2 gives computational results in terms of solution times.
We solve this case study with sample sizes 200, 100, 50 and 25 scenarios. The solutions of the deterministic problem considering the average demand levels for these scenarios are 68,236.4, 67,276.5, 66,256.3 and 66,345.6 million. As we can see in Table 2, the resulting Fullspace models are hard to solve. While all of them can be solved at optimal level, it takes 7,061 second (almost two hours) with number of 105 iterations to solve 200 scenario. Hybrid Lagrangian algorithms obtain the optimal solution, which takes 3,151 second (almost one hours) with 2% Optimality gap. For 100, 50 and 25 scenario, the algorithm is terminated after a times limit of 1,061, 531 and 421 second with a remaining optimality gap of 1.6%, 2.6% and 1.8%, respectively. In these cases, the optimality gap does not close after a large number of iterations (112, 142 and 136, respectively). In contrast, the cross decomposition algorithm (the combination of Benders decomposition and hybrid Lagrangian relaxation algorithms) solves all four scenario to optimality, without optimality gap and outperforms the Fullspace model in terms of runtime by 93.3%, 83.1%, 74.9% and 38.2% for 200, 100, 50 and 25 scenario, respectively.
In comparison with hybrid Lagrangian relaxation algorithms, cross decomposition methods always take fewer iterations due to its strong hybrid Lagrangian relaxation algorithms and Benders decomposition bounds. The convergence of this technique regarding the convergence of Benders decomposition method in finite iteration numbers is guaranteed. However, the gains in terms of iterations and stronger lower bounds come with the price of additional computational time that is required to solve the Lagrangian dual subproblem and the Lagrangian master problem in each iteration. As the problem size increases, the strong bounds obtained by the hybrid Lagrangian part of the cross decomposition become more powerful and have a bigger impact.
7. CONCLUSION
In this paper, we presented a twostage mixedinteger linear stochastic programming approach for the strategic planning of a multiproduct, multiperiod supply chain investment planning problem under demand uncertainty. We developed a comprehensive framework for solving the problem based on hybrid Lagrangian relaxation, Benders decomposition and Cross decomposition, exploiting its scenario decomposable structure. In this context, the use of decomposition itself presented as being imperative, due to the large size of the fullspace problem. We also presented a novel hybrid Lagrangian relaxation algorithm framework for to update the Lagrangian multiplier set, based on the combination of cuttingplane, subgradient, and trustregion strategies. Numerical results suggest that significant savings in computational times can be achieved by using the proposed strategy.