A hybrid scenario cluster decomposition algorithm for supply chain tactical planning under uncertainty

作者：Zanjani Masoumeh Kazemi^*; Bajgiran Omid Sanei; Nourelfath Mustapha

来源：European Journal of Operational Research, 2016, 252(2): 466-476.

DOI：10.1016/j.ejor.2016.01.048

• Multi-stage stochastic programming
• Scenario decomposition
• Lagrangian Relaxation
• Sub-gradient method
• Variable Fixing Heuristic

We propose a Hybrid Scenario Cluster Decomposition (HSCD) heuristic for solving a large-scale multistage stochastic mixed-integer programming (MS-MIP) model corresponding to a supply chain tactical planning problem. The HSCD algorithm decomposes the original scenario tree into smaller sub-trees that share a certain number of predecessor nodes. Then, the MS-MIP model is decomposed into smaller scenario-cluster multi-stage stochastic sub-models coordinated by Lagrangian terms in their objective functions, in order to compensate the lack of non-anticipativity corresponding to common ancestor nodes of sub-trees. The sub-gradient algorithm is then implemented in order to guide the scenario-cluster sub models into an implementable solution. Moreover, a Variable Fixing Heuristic is embedded into the sub gradient algorithm in order to accelerate its convergence rate. Along with the possibility of parallelization, the HSCD algorithm provides the possibility of embedding various heuristics for solving scenario cluster sub-models. The algorithm is specialized to lumber supply chain tactical planning under demand and supply uncertainty. An ad-hoc heuristic, based on Lagrangian Relaxation, is proposed to solve each scenario-cluster sub-model. Our experimental results on a set of realistic-scale test cases reveal the efficiency of HSCD in terms of solution quality and computation time.

• 出版日期2016-7-16