(696a) Oscar: Optimal Scenario Reduction Tool Based On Distance of Uncertainty Distribution and Output Performance

Many computational approaches for solving decision making problems under uncertainty are based on approximating the original uncertainty distribution with finitely many scenarios. Such a method results in the solution of a scenario-based approximation problem. The computational requirements for solving scenario-based optimization models depend on the number of scenarios. While a small number of scenarios may lead to a questionable model by overlooking important events, a large number of scenarios can make the problem intractable. To address this problem, scenario reduction technique can be applied. The objective is to use a smaller number of scenarios to obtain a reasonably good approximation of the original system, so that the computational complexity of the approximation problem can be reduced.

Intuitively, the selected scenarios should lead to reasonably good approximations for the optimization problem. While traditional methods [3,4] focus more on the distribution of the uncertain parameters in the input space, our proposed work tries to also capture the performance of output of decision making. To achieve this objective, we consider not only the probability distance between the original and the reduced distribution, but also minimizing the differences on the best, worst and expected performance on the output performance. The objective is to span the possible output scenarios and to capture the wide range of outcomes in a way that is useful for decision-making.

We proposed a novel optimal scenario reduction framework, OSCAR, aiming at addressing the scenario reduction for general optimization problem. The framework contains two modules. The first module involves a novel single-step scenario reduction algorithm based on mixed integer linear optimization technique [1]. New probabilities are assigned to the preserved scenarios, such that the corresponding reduced probability measure is the closest to the original measure in terms of the Kantorovich distance of probability distributions. While the first module aims at reducing a moderate number (less than 5000) of scenarios, the second module extends the optimal scenario reduction algorithm to a sequential framework [2]. The objective is to make a scenario reduction tool capable of addressing huge number of scenarios (e.g., for a problem with 30 uncertain parameters for which scenarios are generated via 10 discrete points for each uncertain parameter, it has 1030 scenarios). The proposed method first ranks the uncertain parameters based on their effects on the optimal objective using global sensitivity analysis. Then, the parameters are sequentially considered in generating uncertainty scenarios until all the uncertain parameters are studied. This method can essentially reduce the computational effort needed for evaluating all the possible scenarios’ objective, which is often impractical since the number of scenarios exceeds the current computation ability.

The proposed methods are designed for generic optimization problems and have many potential applications in reducing uncertainty representation. Application of OSCAR for planning under uncertainty problems and comparison with existing reduction tool SCENRED [5] will be illustrated.

References:
[1] Z. Li, C.A. Floudas. Optimal Scenario Reduction Framework based on Distance of Uncertainty Distribution and Output Performance: I. Single Reduction via Mixed Integer Linear Optimization. 2013, in preparation.
[2] Z. Li, C.A. Floudas. Optimal Scenario Reduction Framework based on Distance of Uncertainty Distribution and Output Performance: II. Sequential Reduction. 2013, in preparation.
[3] J. Dupacova, N. Growe-Kuska, W. Romisch, Scenario reduction in stochastic programming - An approach using probability metrics, Mathematical Programming, 95 (2003) 493-511.
[4] H. Heitsch, W. Romisch, Scenario reduction algorithms in stochastic programming, Computational Optimization and Applications, 24 (2003) 187-206.
[5] GAMS/SCENRED Documentation, www.gams.com/docs/document.htm