Optimization Online


Scenario Tree Reduction Methods Through Changing Node Values

Zhiping Chen(zchen***at***mail.xjtu.edu.cn)
Zhe Yan(155204053***at***qq.com)

Abstract: To develop practical and efficient scenario tree reduction methods, we introduce a new methodology which allows for changing node values, and an easy-to-calculate distance function to measure the difference between two scenario trees. Based on minimizing the new distance, we first construct a primitive scenario tree reduction model which also minimizes the Wasserstein distance between the reduced tree and the initial tree. To make it appropriate for the reduction of general multi-stage scenario trees, we then construct an improved model which not only performs well for the multi-stage scenario tree reduction but also is supported theoretically by the stability results of stochastic programs. Two approximate algorithms are proposed to solve the primitive model. With them, we design a stage-wise scenario tree reduction algorithm which is superior to the simultaneous backward reduction method in terms of computational complexity, the corresponding reduction algorithm especially for fan-liked trees is also presented. We further design a multi-stage 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 multi-stage portfolio selection demonstrate the practicality, efficiency and robustness of proposed reduction models and algorithms.

Keywords: stochastic programs, scenario tree reduction, probabilistic metric, stability

Category 1: Stochastic Programming

Citation: Research report 3 Department of Computing Science, School of Mathematics and Statistics, Xi'an Jiaotong University, 710049, Xi'an, Shaanxi, P. R. China 3 May, 2016

Download: [PDF]

Entry Submitted: 05/03/2016
Entry Accepted: 05/03/2016
Entry Last Modified: 05/03/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society