(411d) Optimal Scenario Tree Generation for Stochastic Programming Using Sinkhorn Distance

Practical optimization applications need to account for uncertainty from various sources to obtain realistic solutions. Stochastic programming (Dantzig, 1955) is a class of methods of optimization under uncertainty, which assumes that the probability distribution of the uncertainty is known or can be estimated. Scenario-based stochastic programming has been developed in which the optimization problem is solved for a finite set of scenarios or discrete realizations of uncertainty. However, the complexity of the stochastic optimization problem, and subsequently, the computational time, increases drastically with an increase in the number of scenarios. Therefore, finding the optimal set of scenarios is a significant research objective.

Scenario reduction is an important way for scenario generation. The concept of scenario reduction was pioneered by Dupacova, et. al (2003), who put forth the idea of obtaining the closest subset from a larger superset of scenarios, using a natural probability metric as an approximation metric. The authors proposed the use of Fortet-Mourier metrics for the reduction of electrical load scenario trees used for power management under uncertainty. The stability of multistage stochastic programs was analyzed by Heitsch, et. al (2006) who posited that the reduction of multistage scenario trees should be based on L_r distances as well as filtration distances. Subsequently, Heitsch and Romisch (2009) derived algorithms for the reduction of multistage scenario trees using this idea. Chen, et. al (2012) developed algorithms using K-means clustering and LP moment matching methods to approximate multistage scenario trees from a large scenario fan description of the uncertain. Floudas and Li (2014) treated the scenario reduction problem as a mixed integer linear programming (MILP) problem. Li, et. al (2016) proposed a computationally efficient algorithm for scenario reduction that circumvents the limitations posed by the aforementioned MILP formulation through the use of transportation distance. In recent work by Zhou, et. al (2019), the authors introduce an improved K-means based on typicality degree (IKBTD) approach for scenario reduction.

In this work, we proposed replacing the linear programming (LP) problem associated with transportation distance calculation between original and reduced scenario sets, in the approach proposed by Li, et. al (2016), by the solution to the entropy-regularized transport problem, termed as the Sinkhorn Distance (Cuturi, et. al (2013)). Computationally, the Sinkhorn Distance was found to be more resource efficient than solving the LP transportation problem, especially for very large scenario supersets, as it comprises an iterative calculation procedure to obtain the optimal transport plan, and distance, using the Sinkhorn-Knopp algorithm. The performance of the proposed algorithm using Sinkhorn Distance was analyzed based on – 1) the approximation quality of the optimal reduced subset with respect to the original scenario superset, and 2) the stability of the scenario reduction method. The approximation quality of the proposed algorithm was contrasted with that of the conventional K-means clustering algorithm (Chen, et. al (2012)) by illustrating the reduction of a large scenario fan generated from a random walk process to a multistage scenario tree and using the Kantorovich Distance (KD) as a measure of dissimilarity between the fan and the generated tree. It was found that the proposed algorithm gives a lower KD, thereby generating a scenario tree structure that is more similar to the original fan than the conventional K-means clustering approach. The stability of the proposed algorithm was assessed by checking for both in-sample and out-of-sample stability (Kaut and Wallace (2003)) of the reduced scenario tree’s solution with respect to the true solution, by testing it on the two-stage stochastic programming formulation of the farmer’s problem (Birge and Louveaux (2011)). We found that the proposed algorithm using the Sinkhorn Distance performs well on both fronts, thus making it a suitable method for reduction of large multistage scenario trees in stochastic programming applications.

References

Dantzig, G. (1955). Linear Programming under Uncertainty. Management Science, 1(3/4), 197-206.

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

Heitsch, H., Römisch, W., & Strugarek, C. (2006). Stability of multistage stochastic programs. SIAM Journal on Optimization, 17(2), 511-525.

Heitsch, H., & Römisch, W. (2009). Scenario tree reduction for multistage stochastic programs. Computational Management Science, 6(2), 117-133.

Xu, D., Chen, Z., & Yang, L. (2012). Scenario tree generation approaches using K-means and LP moment matching methods. Journal of Computational and Applied Mathematics, 236(17), 4561-4579.

Papavasiliou, A., & Oren, S. S. (2013). Multiarea stochastic unit commitment for high wind penetration in a transmission constrained network. Operations Research, 61(3), 578-592.

Li, Z., & Floudas, C. A. (2014). Optimal scenario reduction framework based on distance of uncertainty distribution and output performance: I. Single reduction via mixed integer linear optimization. Computers & Chemical Engineering, 70, 50-66.

Li, Z., & Li, Z. (2016). Linear programming-based scenario reduction using transportation distance. Computers & Chemical Engineering, 88, 50-58.

Zhou, Y., Shi, L., & Ni, Y. (2019, May). An Improved Scenario Reduction Technique and Its Application in Dynamic Economic Dispatch Incorporating Wind Power. In 2019 IEEE Innovative Smart Grid Technologies-Asia (ISGT Asia) (pp. 3168-3178). IEEE.

Cuturi, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in neural information processing systems (pp. 2292-2300).

Kaut, M., & Wallace, S. W. (2003). Evaluation of scenario-generation methods for stochastic programming.

Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media.