(433e) Stable Two-Stage Scenario Tree Generation Method Via a Game-Theoretic Optimization Approach

Towards a robust confrontation of the demanding real-world problems in the modern-day process industries, the study of optimization problems under uncertainty is imperative. Among a variety of optimization-based approaches, Stochastic Programming is a risk neutral modelling method, where t optimization problems can be solved as two-stage or multi-stage stochastic programs. Uncertainty is typically modelled via a finite number of realizations with specified values and probabilities of occurrence, which are also called scenarios [Li and Grossmann, 2021].

Despite the easy formulation of stochastic programs, the usually large amount of uncertain parameters and data can lead to computationally challenging or even intractable problems. Thus, the research interest has been directed on development of approaches for the mitigation of such drawbacks. For instance, critical works on scenario generation or reduction approaches intent to create a smaller set of scenarios, which is representative of the stochastic process [King and Wallace, 2012].

The efficiency of a scenario generation method is crucial for the solution of a stochastic program and several measures are proposed in the literature. Typical examples can include evaluation of the quality of the stochastic solutions [Bayraksan and Morton, 2006], or of the stability of the scenario generation methods [Kaut and Wallace, 2007]. According to the latter, for the generation of a certain number of scenarios, a scenario generation method is considered stable when the scenario-based problem is solved accurrately regardless of the tree generated. Particularly, this is the case for sampling methods. In the contrary, the stability of deterministic approaches can be assessed by calculating the related measures for an increasing number of generated scenarios.

Several approaches for scenario generation are studied in the literature and optimisation-based techniques constitute an important category of them [Li et al., 2020]. Moment Matching Problem (MMP) constitutes a well-known scenario tree generation approach, which is based on the minimization of the errors regarding the considered statistical properties between the original uncertain set and the final reduced set [Høyland and Wallace, 2001]. In general, MMPs are modelled as nonlinear programming (NLP) problems. Parallel matching of the stochastic distribution of the uncertain parameter (DMP), by additionally minimizing the errors regarding the cumulative distribution function, has been proposed and enhances the quality of the approximation [Calfa et al., 2014]. Although, this method is focused on a good approximation of the uncertain distribution in the statistical sence and can lead to stochastic solutions of good quality, it may lack of stability as it suffers from under-specificity issues. Practically, the method may result to scenario trees in which multiple scenarios receive the same values or zero probability of occurrence. This is a consequence of several reasons including the nonlinear programming formulation and the user-defined parameters regarding the weights of the statistical properties, which may lead to overestimation or underestimation of their corresponding errors.

In this work, the proposed Mixed-Integer Linear Programming (MILP) model for the DMP, which is also integrated with a clustering method, resolves the under-specificity issues of its NLP-based counterparts. Furthermore, a modification of the latter model is proposed, in which the Nash bargaining approach is employed within the considered statistical properties and the DMP remains MILP by applying a separable programming approach [Charitopoulos et al., 2020; Gjerdrum et al., 2001]. Exploiting the game-theoritic approach the drawbacks regarding the user-defined parameters are alleviated. Hence, stability of the proposed MILP-based scenario generation methods is compared with state-of-the-art optimisation-based scenario generation approaches. Through a number of case studies on two-stage stochastic programming problems, the benefits regarding in-sample and out-of-sample stability are highlighted.

References

1. Bayraksan, G., & Morton, D. P. (2006). Assessing solution quality in stochastic programs. Mathematical Programming, 108(2), 495–514.
2. Calfa, B. A., Agarwal, A., Grossmann, I. E., & Wassick, J. M. (2014). Data-driven multi-stage scenario tree generation via statistical property and distribution matching. Computers & Chemical Engineering, 68, 7–23.
3. Charitopoulos, V. M., Dua, V., Pinto, J. M., & Papageorgiou, L. G. (2020). A game-theoretic optimisation approach to fair customer allocation in oligopolies. Optimization and Engineering, 21(4), 1459–1486.
4. Gjerdrum, J., Shah, N., & Papageorgiou, L. G. (2001). Transfer prices for multienterprise supply chain optimization. Industrial and Engineering Chemistry Research, 40(7), 1650–1660.
5. Høyland, K., & Wallace, S. W. (2001). Generating Scenario Trees for Multistage Decision Problems. Management Science, 47(2), 295–307.
6. Kaut, M., & Wallace, S. W. (2007). Evaluation of scenario-generation methods for stochastic programming. Pacific Journal of Optimization, 3.
7. King, A. J., & Wallace, S. W. (2012). Modeling with Stochastic Programming.
8. Li, C., & Grossmann, I. E. (2021). A Review of Stochastic Programming Methods for Optimization of Process Systems Under Uncertainty. Frontiers in Chemical Engineering, 2, 34.
9. Li, J., Zhou, J., & Chen, B. (2020). Review of wind power scenario generation methods for optimal operation of renewable energy systems. Applied Energy, 280, 115992.