Optimal Scenario Reduction Method for Stochastic Programming via Probabilistic Similarity Function

In the scenario-based stochastic programming problems, the computational burden increase as the number of scenarios increases, which involves necessary scenario reduction operations. For the scenario reduction problem with high-dimensional random vector, an optimal reduction framework is presented to eliminate redundant scenarios. In this framework, the concept of probabilistic similarity function is firstly proposed to solve the problem that scenarios cannot be clearly distinguished by traditional distance-based reduction methods in the high-dimensional scenario clustering process. The relative distance under each dimension of scenarios is considered in the computation of probabilistic similarity function, which depends not only on the values of two scenario vectors but also on the overall scenario set. The proposed recursive-type reduction method aims at maximizing the probabilistic similarity between the original scenario set and reduced scenario set. The numerical results demonstrate that our method can exhibit better performance than distance-based methods and have good universality for different stochastic programming problems.

I. Introduction

Nowadays, there are a large number of uncertain factors in the real world. Stochastic programming (SP) considers these factors and provides an effective mathematical means to make the decision results better satisfy the needs of practical situation. Thus, it plays an increasingly important role in solving complex decision-making problems. As a crucial ingredient in the programming model, the reasonable representation and determination of the random variables is the key part to solve SP. Scenario analysis can accurately characterize the dynamic evolution path of multiple random variables at each stage through a serious of large-scale scenario sets by statistical approximation [1]. The computational burden and solving efficiency of SP are directly related to the number of scenarios. In order to avoid the intractable solving problem of SP caused by large-scale initial scenario set, it is necessary to take some measures to reduce the redundant scenarios, so as to obtain a smaller representative subset that can well approximate the statistical characteristics of the initial scenarios. Therefore, scenario reduction has become an important operation and research hotspot in the field of SP.