Research Topic

Optimization plays a central role in decision-making in industrial contexts, where uncertainty poses significant challenges. Many problems in this domain are modeled as stochastic programs, which, when solved, produce decisions that mitigate the uncertainty involved in decision-making [1]. The research proposed in this internship focuses on so-called two-stage stochastic linear programs. Typically, these assume a finite representation of uncertainty represented as a discrete set of scenarios capturing historical or estimated realizations of uncertain parameters. However, the computational complexity of solving such programs increases with the number of scenarios, rendering large-scale problems intractable. This phenomenon is known as the curse of dimensionality [1]. To overcome this, scenario clustering methods have a lot of attention in the stochastic programming literature. These group similar scenarios to construct reduced models that preserve the original scenario set’s essential information [3, 7].

Although these approaches reduce computational complexity, they often lack guarantees regarding the quality of the solution obtained relative to the orig- inal problem [4, 5]. To address these challenges, researchers have developed integrated approaches that combine clustering with optimization techniques [8, 6]. However, the literature reveals two major gaps: (1) there is no unified mathematical description of scenario clustering methods, and (2) existing integrated approaches often focus on specific stochastic optimization problems or require restrictive assumptions on the uncertain parameters that drive the decision making.

This internship aims to explore a new perspective on scenario clustering using matrix-theoretic tools. By leveraging these tools, we aim to unify existing clustering methods and study their impact on optimization models. Additionally, this perspective will enable the development of novel computational approaches that integrate clustering and optimization, with broad applicability to generic two-stage stochastic programs. The intern will investigate the mathematical structure of clustering matrices and their role in constructing inner and outer approximations of stochastic models. This work will address fundamental research questions, such as the design of efficient clustering methods, their impact on computational tractability, and their influence on solution quality.

References

1. John R Birge and Francois Louveaux. Introduction to stochastic program-
   ming. Springer Science & Business Media, 2011.
2. Steven L Brunton and J Nathan Kutz. Data-driven science and engineering:
   Machine learning, dynamical systems, and control. Cambridge University
   Press, 2022.
3. Holger Heitsch and Werner Römisch. “Scenario reduction algorithms in
   stochastic programming”. In: Computational Optimization and Applica-
   tions 24 (2003), pp. 187–206. doi: 10.1023/A:1021805924152.
4. Julien Keutchayan, Janosch Ortmann, and Walter Rei. “Problem-driven
   scenario clustering in stochastic optimization”. In: Computational Man-
   agement Science 20.1 (2023), p. 13. doi: 10.1007/s10287-023-00446-2.
5. Juan M Morales et al. “Scenario reduction for futures market trading in
   electricity markets”. In: IEEE Transactions on Power Systems 24.2 (2009),
   pp. 878–888. doi: 10.1109/TPWRS.2009.2016072.
6. Cristian Ramirez-Pico and Eduardo Moreno. “Generalized adaptive partition-
   based method for two-stage stochastic linear programs with fixed recourse”.
   In: Mathematical Programming 196.1-2 (2022), pp. 755–774. doi: 10.1007/
   s10107-020-01609-8.
7. Napat Rujeerapaiboon et al. “Scenario reduction revisited: Fundamental
   limits and guarantees”. In: Mathematical Programming 191.1 (2022), pp. 207–
   242. doi: 10.1007/s10107-018-1269-1.
8. Yongjia Song and James Luedtke. “An adaptive partition-based approach
   for solving two-stage stochastic programs with fixed recourse”. In: SIAM
   Journal on Optimization 25.3 (2015), pp. 1344–1367. doi: 10.1137/140967337.