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

Masoumeh Kazemi Zanjani, Omid Sanei Bajgiran and Mustapha Nourelfath

European Journal of Operational Research, 2016, vol. 252, issue 2, 466-476

Abstract: We propose a Hybrid Scenario Cluster Decomposition (HSCD) heuristic for solving a large-scale multi-stage 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.

Keywords: Multi-stage stochastic programming; Scenario decomposition; Lagrangian Relaxation; Sub-gradient method; Variable Fixing Heuristic (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171600093X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:252:y:2016:i:2:p:466-476

DOI: 10.1016/j.ejor.2016.01.048

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().