Computers & Chemical Engineering, Vol.109, 96-111, 2018
Scenario tree reduction methods through clustering nodes
To develop practical and efficient scenario tree reduction methods, we introduce a new methodology which depends on clustering nodes, and thus an easy-to-handle distance function to measure the difference between two scenario trees is designed. On the basis of minimizing the new distance, we constructa multiperiod scenario tree reduction model which is supported theoretically by the stability results of stochastic programs. By solving the model, we design a stage-wise scenario tree reduction algorithm which is superior to the simultaneous backward reduction method in terms of both computational complexity and solution results of stochastic programming problems, the corresponding reduction algorithm especially for fan-liked trees is also presented. We further design a multiperiod scenario tree reduction algorithm with a pre-specified distance by utilizing the stability results of stochastic programs. A series of numerical experiments with real trading data and the application to multiperiod portfolio selection problem demonstrate the practicality, efficiency and robustness of proposed reduction model and algorithms. (C) 2017 Elsevier Ltd. All rights reserved.
Keywords:Stochastic programs;Scenario tree reduction;Clustering;Stability;Computational efficiency;Portfolio selection