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. set of harvesting blocks set of manufacturing mills set of raw materials set of available raw material scenarios set of time periods corresponding to node n in the scenario tree the demand scenario tree set of immediate predecessor of each node n in scenario tree the total harvesting capacity in period t the total transportation capacity in period t unit cost to harvest block bl during period t unit cost to transport raw material rm from block bl to mill m during period t unit cost to store raw material rm in block bl during period t stumpage fee for raw material rm in block bl during period t inventory holding cost of raw material rm at mill m inventory capacity at mill m during period t supply capacity of block bl in period t maximum number of periods over which harvesting can occur in block bl lead time of procuring raw material rm from block bl unit purchase cost of raw material rm from block m in period t maximum number of blocks in which harvesting can occur during period t probability of node n in scenario tree probability of supply scenario sc minimum contract purchase quantity from block bl safety stock of raw material rm at mill m volume of available raw material rm in block bl for supply scenario sc forecasted demand of raw material rm for mill m in period t at node n of the scenario tree binary variable that takes 1 if harvesting occurs in block bl during time period t at node n of the scenario tree and 0 otherwise inventory of raw material rm in block bl at the end of period t for supply scenario sc at node n of the scenario tree inventory of raw material rm at mill m at the end of period t for supply scenario sc at node n of the scenario tree purchasing quantity of raw material rm from block bl in period t at node n of the scenario tree proportion of harvested block bl in period t at node n of the scenario tree 
A hybrid scenario cluster decomposition algorithm for supply chain tactical planning under uncertainty