Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.18 No.1 pp.132-142

A Cross Decomposition Approach for the Optimization of the Petroleum Product Supply Chain

Hadi Mohammadi, Esmaile Khorram*
Department Mathematics and Computer, Amirkabir University of Technology, Tehran, Iran
Corresponding Author, E-mail:
July 17, 2018 November 30, 2018 December 26, 2018


This paper addresses the solution of a two-stage stochastic mixed integer programming model for an investment of planning problems applied to the petroleum products supply chain. In this context, we present the development of decomposition techniques for the stochastic Benders decomposition and Lagrangian relaxation methods. The combinational technique of cross decomposition is a suitable one for exact solution of the mixed integer programming problems which uses simultaneously the advantages of Lagrangian relaxation and Benders decomposition methods that each reinforces one another.

The basic idea for this technique is the generation of suitable upper and lower bounds for the optimal value of the original problem at each iteration. In this paper, as far as cross decomposition algorithm is concerned, we present a new hybrid Lagrangian relaxation algorithm for updating the Lagrangian multiplier set, based on the combination of cutting-plane, sub-gradient and trust-region strategies. The convergence of this technique regarding the convergence of Benders decomposition method in finite iteration numbers has been guaranteed.

Results suggest that the proposed approach is able to efficiently solve the problem under consideration, achieving better performance in terms of computational times as compared to other techniques.



    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 L-Shaped calculation into the setting of stochastic integer programming problems using convexification procedures for the second-stage 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 sub-gradient 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 sub-problem 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 sub-problem 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 sub-problem is a passage for other master problem. As it is the master problem of any strategy is fortified with the acquired data out of sub-problems.

    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 sub-problems) 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 multi-product, multi-period 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 cutting-plane, sub-gradient 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.


    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 multi-product and multi-period 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 multi-period 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.


    Considering an arrangement of items that are provided from a few multi-product 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 multi-period 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 two-stage 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 first-stage 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 second-stage 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 second-stage 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.


    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:

    m i n w , y 0 , 1 j , p , t W j p t w j p t + i , j , t Y i j t y i j t + φ w , y

    s . t . t w j p t 1 , j B , p Ρ

    t y i j t 1 , i , j Ν

    where wjpt represents the capacity expansion investment decisions at location j for product p and in period t, and yijt represents the investment decisions for arcs connecting locations i and j in period t. φ ( w , y ) = Ε Ω Q ( w , y , ξ ) 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.

    φ w , y = min x , v R + , z 0 , 1 ξ P ξ i , j , p , t C i j t x i j p t ξ + j , p , t H j p t v j p t ξ + j , t S j t z j t ξ

    s . t . i x i j p t ξ + v j p t 1 ξ = i x i j p t ξ + v j p t ξ + D j p t ξ , j B , p Ρ , t τ , ξ Ω

    j x i j p t ξ O i p t , i S , p Ρ , t τ , ξ Ω

    j x i j p t ξ A i j o + A i j t ' t y i j t ' , i , j N , t τ , ξ Ω 

    v j p t ξ M j p o + M j p   t ' t w j p t ' + U j t z j t ξ , j B , p Ρ , t τ , ξ Ω

    v j p t ξ L j p + M j p o + M j p t ' t w j p t ' , j B , p Ρ , t τ , ξ Ω

    i x i j p t ξ K j p M j p o + M j p t ' t w j p t ' + U j t z j t   , j B , p Ρ ,   t τ , ξ Ω

    The second-stage problem φ ( w , 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.


    We assume that large-scale instances of the stochastic supply chain investment planning problem 4.1-4.3 presented in Section 4 cannot be solved in full space, and we consider that scenario-case 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 scenario-case 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:

    I P : M i n c T x + f T y

    s . t . A x + B y = b

    D y = d

    x 0

    y 0 , i n t e g e r

    where c R m 1 , f R m 2 , b R n 1 and d R n 2 and also A, B and D are matrixes n 1 ×m 1 , n 1 ×m 2 and n 2 ×m 2 respectively. The variables of x R m 1 are continuous and the integer and complex variables of y R 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 sub-problem 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 sub-problem is written as follows:

    L S P : L λ = M i n         c T x + f T y + λ ( D y d )

    s . t .         A x + B y = b

    x 0

    y 0 , i n t e g e r

    where λ (Lagrangian multiplier) is a real, positive and adequately large enough value. Let x ˜ k , y ˜ k be the optimal solution of LSPk considered. We call the above model Lagrangian sub-problem. In some of the problems by considering the problem structure this sub-problem can be decomposed to segregate sub-problems (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 λ,

    z * = min c T x + f T y Ax + By = b , Dy = d , x 0 , y 0 , integer = min c T x + f T y + λ ( Dy d ) Ax + By = b , x 0 , y 0 , integer   

    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), z * L λ . □

    To obtain the sharpest possible lower bound, we would need to solve the following optimization problem:

    L D = Max λ L λ

    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 LD of the Lagrangian dual (20) is a lower bound on the value z* of an optimal solution of IP, i.e. L D z * .

    Proof. For any Lagrangian multiplier λ and for any feasible solution x of problem IP, we have L λ L D z * . .□

    There are different methods for solving the following problem that one classic method is sub-gradient 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 sub-gradient 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 sub-gradient, 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:

    L M P : L D k + 1 = M a x η + δ 2 λ λ ¯ 2 2

    s . t . η   c T x ˜ k + f T y ˜ k + λ k y ˜ k d

    λ k + 1 = λ k + β υ ( L D k ) υ ( L λ k ) D y ˜ k d 2 ( D y ˜ k d )

    k = 1 , , K , η ϵ R , α ϵ R , λ ϵ R β ϵ , β ¯ , δ ϵ δ ¯ , δ ¯ , λ ¯ > 0

    where, therein υ (LD) 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 sub-gradient 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:

    υ L D k υ ( L λ k ) ε

    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:

    P S P : M i n y ¯ Y f T y ¯ + M i n x 0 c T x : A x = b B y ¯

    where therein is:

    Y = y Dy = d , y 0 , integer

    Let x ^ k have the optimal solution of PSPk. The inner minimization is a continuous linear problem that can be dualized by dual variables u as follows:

    D S P : M a x u R n 1 u T b B y ¯ : u T A c

    Let uk have the optimal solution of DSPk. In the Benders decomposition algorithm, we consider the relationship (26) as Benders sub-problem. With regard to the duality theorem we can write the relation (25) as follows:

    M i n y ¯ Y f T y ¯ + M a x u R n 1 u T b B y ¯ : u T A c

    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 ( u i T s is the vector that corresponds to the extreme points I of the dual of PSP and u i T s is the vector that corresponds to the extreme rays J of the dual of PSP):

    BMP : Min f T y +​ z

    s . t . D y = d

    u i T b By z ,     i I

    u j T b By 0 ,     j J

    y 0 , integer

    Let yk have the optimal solution of BMPk. 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 sub-problem, 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 first-stage solutions that are feasible regarding the first-stage constraints (in contrast to using a heuristic as in Lagrangian decomposition). Furthermore, we use a multi-cut 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 sub-problems of each of the methods are solved in parallel and these sub-problems 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.


    • 1. initialization k = 0 , K = { 0 } , y k = 0 = 0 , λ k = 0 = 0 , L B = , U B = .

      Go to step 2.

    • 2. Benders sub-problem For given yk solve (BSPk)

      Store solution uk, if υ ( B S P k ) < U B set U B = υ ( B S P k ) and go to step 3.

    • 3. Lagrangian sub-problem For given λk solve (LSPk) in parallel

      Store x ˜ k , y ˜ k and υ ( L S P k ) and go to step 4.

    • 4. Lagrangian master problem For given x ˜ k and y ˜ k solve ( L M P k + 1 ).

      Store solution for Lagrangian multipliers and set λ k + 1 and update β, δ and λ and go to step 5.

    • 5. Benders master problem For given u k , υ ( L S P k ) and kK solve ( B M P k + 1 ). Store solution for y k + 1 . .

      If L B < υ ( B M P k + 1 ) , , set L B = υ ( B M P k + 1 ) and go to step 6 otherwise go to step 2.

    • 6. Check convergence(optimality) If U B L B ε stop.

      Else set k= k +1 and include in K; go back to step 2.


    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 full-space 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 full-space model, hybrid Lagrangian relaxation algorithms (the combination of cutting-plane, sub-gradient 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 multi-scale definition for the time horizon in regard to investment (first-stage) decisions and planning (second-stage) 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 Homem-de 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 Full-space 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 Full-space 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 sub-problem 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.


    In this paper, we presented a two-stage mixedinteger linear stochastic programming approach for the strategic planning of a multi-product, multi-period 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 full-space problem. We also presented a novel hybrid Lagrangian relaxation algorithm framework for to update the Lagrangian multiplier set, based on the combination of cuttingplane, sub-gradient, and trust-region strategies. Numerical results suggest that significant savings in computational times can be achieved by using the proposed strategy.



    Network representation under a multi-period planning framework.


    Cross decomposition algorithm.


    APPENDIX A. Nomenclature

    Model notation

    Deterministic equivalent sizes

    Computational results


    1. Barahona, F. and Anbil, R. (2000), The volume algorithm: producing primal solutions with a sub-gradient method, Mathematical Programming, 87(3), 385-399.
    2. Benders, J. F. (1962), Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4(1), 238-252.
    3. Carøe, C. C. and Schultz, R. (1999), Dual decomposition in stochastic integer programming, Operations Research Letters, 24(1-2), 37-45.
    4. Cheney, E. W. and Goldstein, A. A. (1959), Newton’s method for convex programming and Tchebycheff approximation, Numerische Mathematik, 1(1), 253-268.
    5. Christopher, M. (2016), Logistics & supply chain management, Pearson UK.
    6. Elsaghier, E. H. (2017), Planning and optimising of petroleum industry supply chain and logistics under uncertainty, Ph.D. dissertation, Sheffield Hallam University, Sheffield, UK.
    7. Held, M. and Karp, R. M. (1971), The traveling-salesman problem and minimum spanning trees: Part II, Mathematical Programming, 1(1), 6-25.
    8. Held, M. , Wolfe, P. , and Crowder, H.(1974), Validation of subgradient optimization, Mathematical Programming, 6(1), 62-88.
    9. Holmberg, K. (1990), On the convergence of cross decomposition, Mathematical Programming, 47(1-3), 269-296.
    10. Kelley, J. E. (1960), The cutting-plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics, 8(4), 703-712.
    11. Laporte, G. and Louveaux, F. V. (1993), The integer Lshaped method for stochastic integer programs with complete recourse, Operations Research Letters, 13(3), 133-142.
    12. Lemaréchal, C. (1989), Nondifferentiable optimization, Handbooks in Operations Research and Management Science, 1, 529-572.
    13. Li, Z. and Ierapetritou, M. G. (2012), Capacity expansion planning through augmented Lagrangian optimization and scenario decomposition, AIChE Journal, 58(3), 871-883.
    14. Marsten, R. E. , Hogan, W. W. , and Blankenship, J. W. (1975), The box step method for large-scale optimization, Operations Research, 23(3), 389-405.
    15. Melo, M. , Nickel, S. , and Saldanha-Da-Gama, F.(2009), Facility location and supply chain management: A review, European Journal of Operational Research, 196(2), 401-412.
    16. Mitra, S. , Garcia-Herreros, P. , Grossmann, I. E.(2016), A cross decomposition scheme with integrated primal– dual multi-cuts for two-stage stochastic programming investment planning problems, Mathematical Programming, 157(1), 95-119.
    17. Mouret, S. , Grossmann, I. E. , and Pestiaux, P.(2011), A new Lagrangian decomposition approach applied to the integration of refinery planning and crude-oil scheduling, Computers and Chemical Engineering, 35(12), 2750-2766.
    18. Norkin, V. I. , Ermoliev, Y. M. , and Ruszczyński, A.(1998), On optimal allocation of indivisibles under uncertainty, Operations Research, 46(3), 381-395.
    19. Oliveira, F. and Hamacher, S. (2012), Optimization of the petroleum product supply chain under un-certainty: A case study in northern Brazil, Industrial & Engineering Chemistry Research, 51(11), 4279-4287.
    20. Oliveira, F. , Gupta, V. , Hamacher, S., Grossmann, I. E.(2013), A lagrangian decomposition approach for oil supply chain investment planning under uncertainty with risk considerations, Computers and Chemical Engineering, 50, 184-195.
    21. Redondo, N. and Conejo, A. (1999), Short-term hydrothermal coordination by Lagrangian relaxation: Solution of the dual problem, Power Systems, IEEE Transactions, 14(1), 89-95.
    22. Ruszczynski, A. (1995), On convergence of an augmented Lagrangian decomposition method for sparse convex optimization, Mathematics of Operations Research, 20(3), 634-656.
    23. Sahinidis, N. V. (2004), Optimization under uncertainty: State-of-the-art and opportunities, Computers & Chemical Engineering, 28(6-7), 971-983.
    24. Shapiro, A. and Homem-de Mello, T. (1998), A simulation- based approach to two-stage stochastic programming with recourse, Mathematical Programming, 81(3), 301-325.
    25. Sherali, H. D. and Fraticelli, B. M. P. (2002), A modication of benders’ decomposition algorithm for discrete sub-problems: An approach for stochastic programs with integer recourse, Journal of Global Optimization, 22(1-4), 319-342.
    26. Van Roy, T. J. (1983), Cross decomposition for mixed integer programming, Mathematical Programming, 25(1), 46-63.
    27. Zhao, X. and Luh, P. B. (2002), New bundle methods for solving Lagrangian relaxation dual problems, Journal of Optimization Theory and Applications, 113(2), 373-397.
    28. Zheng, Q. P. , Wang, J. , Pardalos, P. M., and Guan, Y.(2013), A decomposition approach to the two-stage stochastic unit commitment problem, Annals of Operations Research, 201(1), 387-410.