Linear programming-based scenario reduction using transportation distance

• A new computationally efficient scenario reduction algorithm is proposed.
• The proposed method avoids the combinatorial limitation of the MILP-based method.
• The proposed method can efficiently reduce scenarios with acceptable solution time.
• The proposed scenario reduction method outperforms the SCENRED2 tool.

One of the major difficulties for scenario-based decision-making problems (e.g. stochastic programming using scenarios) is that the problem complexity quickly increases as the number of scenarios increases. Scenario reduction aims at selecting a small number of scenarios to represent a large set of scenarios for decision making, so as to significantly reduce the computational complexity while preserving the solution quality of using a large number of scenarios. In this work, a new computationally efficient scenario reduction algorithm is proposed based on transportation distance minimization. The proposed algorithm relies on solving linear programming problems. The scenario subset updating step and the probability value assignment step are performed in an iterative manner until the transportation distance converges. Comparison with existing scenario reduction methods reveals that the proposed method is very efficient for the reduction of large scenario set. Application studies on stochastic optimization problems also demonstrate the effectiveness of the proposed method.