(346b) A Linear Programming Based Scenario Reduction Approach Using Transportation Distance

Uncertainty is pervasive in various process design and operations problems. In the corresponding optimization problems, uncertainty is often represented using samples/scenarios (e.g., stochastic programming with recourse, sample average approximation for chance constrained optimization). For the solution of the scenario based optimization problem, the quality of the solution is greatly affected by the scenarios used. In general, using a large number of scenarios can lead to higher solution reliability, but result in higher computational complexity. For many optimization problems under uncertainty, the scenario based model even becomes intractable by including a large number of scenarios into the model. Scenario reduction, an important topic of scenario based decision making, is induced with the aim of selecting a few representative scenarios from a large number of scenarios. The selected scenarios will then be used in the scenario based optimization model, so as to reduce the computational complexity.

Although it is an important topic, scenario reduction has received limited attention in literature [1-3]. Among the existing methods, the transportation distance [4] based scenario reduction was shown to be one of the most effective methods. Along this direction, a heuristic based scenario reduction method for stochastic programming was proposed in [5] and a corresponding tool SCENRED2 is available in GAMS. Li and Floudas [6] proposed a mixed integer linear optimization (MILP) based scenario reduction method, which rigorously minimizes the transportation distance (i.e., Kantorovich distance) to find the optimal subset to represent the initial superset of scenarios. This method also considers the performance of input and output space simultaneously. Although the MILP based scenario method can provide the optimal reduced subset of scenarios, the method is limited by the size of the problem. With the state-of-the-art mixed integer linear optimization solver, the method can only address moderate number of scenarios (i.e., up to 5000). Li and Floudas [7] recently proposed a method for the reduction of the huge number of scenarios (e.g., 5³⁰) generated from the factorial combination. A sequential reduction framework was proposed which significantly reduce the computational complexity. Some criteria for quantifying the quality of scenario reduction were also proposed considering that it is impractical to evaluate huge number of scenarios.

In this work, a linear programming (LP) based scenario reduction method is proposed. The objective is to address the reduction from a given large set of scenarios (much more than 5000, and not necessarily generated from the factorial combination). In the proposed algorithm, the selected scenarios and the corresponding probabilities are updated in two successive steps in an iterative fashion. The first step calculates the probabilities based on a fixed selection of scenarios and the second step updates the subset of selected scenarios. The first step is solved based on a simple linear programming problem and the second step only relies on simple cost calculations. Hence, the computational complexity of the proposed method is much less than the existing MILP based method. The proposed method works well for those scenario sets with a large size (i.e., 50000). The proposed algorithm will be illustrated with various case studies. We will also demonstrate the effectiveness of the proposed method through comparison studies with SCENRED2 [5] and the MILP based scenario reduction method [6].

References:

[1].      Dupačová J, Gröwe-Kuska N, Römisch W. Scenario reduction in stochastic programming[J]. Mathematical Programming. 2003,95(3):493-511.

[2].      Heitsch H, Römisch W, Strugarek C. Stability of multistage stochastic programs[J]. SIAM Journal on Optimization. 2006,17(2):511-25.

[3].      Karuppiah R, Martín M, Grossmann IE. A simple heuristic for reducing the number of scenarios in two-stage stochastic programming[J]. Computers & Chemical Engineering. 2010,34(8):1246-55.

[4].      Rachev ST, Rüschendorf L. Mass Transportation Problems: Volume I: Theory: Springer Science & Business Media; 1998.

[5].      Heitsch H, Römisch W. Scenario Reduction Algorithms in Stochastic Programming[J]. Computational Optimization and Applications. 2003,24(2-3):187-206.

[6].      Li Z, Floudas CA. Optimal scenario reduction framework based on distance of uncertainty distribution and output performance: I. Single reduction via mixed integer linear optimization[J]. Computers & Chemical Engineering. 2014,70:50-66.

[7].      Li Z, Floudas CA. Optimal scenario reduction framework based on distance of uncertainty distribution and output performance: II. Sequential reduction. Computers & Chemical Engineering. 2015, in publication.