We compare two popular scenario tree generation methods in the context of financial optimization: Moment matching and scenario reduction. Using a simple problem with a known analytic solution, we find that moment matching - accompanied by a check to ensure absence of arbitrage opportunities - replicates this solution precisely. On the other hand, even if the scenario trees generated by scenario reduction are arbitrage-free, the solutions to the approximate optimization problem represented by the reduced tree are biased and highly variable. These results hold for correlated and uncorrelated asset returns, as well as for normal and non-normal returns. (authors' abstract)

[pt] O planejamento de recursos materiais é uma parte importante do gerenciamento da cadeia de suprimentos. As tarefas na cadeia de suprimentos precisam de materiais e recursos para serem executadas e, portanto, alocar os recursos corretamente é uma parte importante do planejamento de tarefas. Especificamente, as tarefas de construção de poços submarinos requerem a utilização de recursos, como sondas, e o planejamento do cronograma dessas operações envolve o dimensionamento de diversos materiais e serviços necessários para sua execução. Este estudo é motivado pelo planejamento de programação real de uma grande empresa de Óleo e Gás que estima estocasticamente a demanda por materiais e serviços devido às incertezas associadas às tarefas em suas datas de início e durações. O cálculo da demanda varia de acordo com o cronograma atual que a empresa possui e a um conjunto de regras que indicam condições de alocação, parâmetros logísticos, condições de desembarque e dependências para alocar as ferramentas e serviços necessários para cada tarefa e estimar sua quantidade e quantos dias em que serão usados. Este conjunto de ferramentas e regras pode mudar dependendo do usuário e de seu conhecimento operacional. Além disso, a empresa utiliza um grande número de cenários, o que resulta em tempos computacionais extremamente altos e impacta a tomada de decisões operacionais. Nesse contexto, a redução de cenários poderia auxiliar a empresa no seu processo de tomada de decisão. A metodologia proposta neste trabalho avalia e identifica cenários representativos de incerteza nos cronogramas de planejamento estratégico de sondas offshore, a fim de reduzir o número de cenários utilizados no cálculo da demanda por ferramentas e serviços. Com a utilização de técnicas não supervisionadas, como k-means e agrupamento hierárquico, foi identificado um subconjunto com os cenários mais representativos para a redução de cenários. A Distância de Wasserstein e a visualizações gráficas foram utilizadas para calcular a representatividade dos cenários selecionados e encontrar o melhor subconjunto. Além disso, o subconjunto de cenários proveniente da redução também foi utilizado para analisar o impacto da redução no cálculo da demanda. O Clustering Aglomerativo com Ward Linkage obteve os melhores resultados de clusterização e representatividade, resultando em um subconjunto de redução de 782 cenários. Para encontrar um conjunto mínimo representativo de cenários, foi utilizado o melhor método de agrupamento, junto com a Distância de Wasserstein, e por fim obtido um número de 343 cenários. Isto apresenta uma redução de 84 por cento no tempo de execução do cálculo da demanda, com o erro maior de 11 por cento no cálculo da demanda. / [en] Material resource planning is an integral part of supply chain management. The tasks in the supply chain need materials and resources to be executed, thus, allocating resources correctly is an important part of task scheduling. Specifically, construction tasks for subsea wells require the use of resources, such as rigs, and planning the schedule of these operations involves the sizing of various materials and services necessary for their execution. This study is motivated by real-life scheduling planning from a large Oil and Gas company that estimates the demand for materials and services stochastically due to the uncertainties associated with the tasks in their start dates and durations. The calculation of the demand is subject to the current schedule that the company has and a set of rules that indicate allocation conditions, logistics parameters, disembarking conditions, and dependencies to allocate the tools and services needed for each task and estimate their quantity and how many days they will be used. These sets of tools and rules can change depending on the user and their operation knowledge. Additionally, the company uses a large number of scenarios, which results in extremely high computational times and impacts operational decision-making. In this context, scenario reduction could assist the company in its decision-making process. The methodology proposed in this work evaluates and identifies representative scenarios of uncertainty in strategic planning schedules of offshore rigs in order to reduce the number of scenarios used in the calculation of the demand for tools and services. With the use of unsupervised techniques, such as k-means and hierarchical clustering, we identified a subset with the most representative scenarios for the scenario reduction. The Wasserstein Distance and graphical visualization were used to measure the representativeness of the selected scenarios and find the best subset. Moreover, the scenario reduction subset was also used to analyze the impact of the reduction in the demand calculation. The Agglomerative Clustering with Ward Linkage (hierarchical clustering) obtained the best clustering evaluation and representativeness metrics, resulting in a selected subset of 782 scenarios. To find a minimal representative set of scenarios, the best clustering method and the Wasserstein Distance were used, resulting in a number of 343 scenarios. This presents a reduction of 84 percent in the execution time of the demand calculation, with the highest error of 11 percent in the demand calculation.

[pt] O uso de abordagens de programação estocástica e redução de cenários tem se tornado imprescindível na análise e predição de comportamento de sistemas dinâmicos. Entretanto, tais técnicas não levam em conta o conhecimento prévio sobre domínio que o usuário possui. O presente trabalho tem por objetivo o desenvolvimento de uma abordagem visual e interativa para abordar o problema de redução de cenários com dados temporais. Para tanto, nós propomos a implementação de uma série de visualizações de dados temporais integradas. Também propomos a adaptação de um algoritmo de projeção multidimensional para lidar com dados temporais. Desta forma, podemos representar graficamente a evolução de um conjunto de cenários ao longo do tempo. Outra visualização proposta no presente trabalho é uma adaptação de Bump chart para lidar com dados temporais acumulados; através dele, um usuário pode comparar a evolução das distâncias entre os diferentes cenários e um cenário de referência. Para validar a nossa proposta, fizemos uma implementação das técnicas propostas e conduzimos um estudo com usuários de diferentes áreas do conhecimento e níveis de experiência. Os resultados obtidos até então indicam que uma abordagem visual para o problema de redução de cenários é viável, e permite a seleção de um conjunto razoável de cenários. Além disso, constatamos que essa abordagem pode ser útil em um contexto de exploração de dados visando a redução de cenários. O usuário também pode explorar visualmente os resultados de outras técnicas de redução de cenários usando nossa abordagem. Os usuários entrevistados reportaram facilidade em cumprir as tarefas propostas e comentaram positivamente sobre os mecanismos de interação fornecidos pelo nosso protótipo. Também testamos os cenários escolhidos usando nossa proposta contra outras abordagens encontradas tanto na literatura quanto em uso na indústria. Os resultados obtidos foram bons, indicando que nossa proposta é viável em casos de uso reais. / [en] Stochastic programming and scenario reduction approaches have become invaluable in the analysis and behavior prediction of dynamic systems. However, such techniques often fail to take advantage of the user s own expertise about the problem domain. This work provides visual interactive support to assist users in solving the scenario reduction problem with timeseries data. We employ a series of time-based visualization techniques linked together to perform the task. By adapting a multidimensional projection algorithm to handle temporal data, we can graphically present the evolution of the ensemble. We also propose to use cumulative bump charts to visually compare the ranks of distances between the ensemble time series and a baseline series. To evaluate our approach, we developed a prototype application and conducted observation studies with volunteer users of varying backgrounds and levels of expertise. Our results indicate that a graphical approach to scenario reduction may result in a good subset of scenarios and provides a valuable tool for data exploration in this context. The users liked the interaction mechanisms provided and judged the task to be easy to perform with the tools we have developed. We tested the proposed approach against state-of-the-art techniques proposed in the literature and used in the industry and obtained good results, thus indicating that our approach is viable in a real-world scenario.

[ES] La gran mayoría de procesos del mundo real tienen incertidumbres inherentes, las cuales, al ser consideradas en el proceso de modelado, se puede obtener una representación que describa con la mayor precisión posible el comportamiento del proceso real. En la mayoría de casos prácticos, se considera que éstas tienen un comportamiento estocástico y sus descripciones como distribuciones de probabilidades son conocidas. Las estrategias de MPC estocástico están desarrolladas para el control de procesos con incertidumbres de naturaleza estocástica, donde el conocimiento de las propiedades estadísticas de las incertidumbres es aprovechado al incluirlo en el planteamiento de un problema de control óptimo (OCP). En éste, y contrario a otros esquemas de MPC, las restricciones duras son relajadas al reformularlas como restricciones de tipo probabilísticas con el fin de reducir el conservadurismo. Esto es, se permiten las violaciones de las restricciones duras originales, pero tales violaciones no deben exceder un nivel de riesgo permitido. La no-convexidad de tales restricciones probabilísticas hacen que el problema de optimización sea prohibitivo, por lo que la mayoría de las estrategias de MPC estocástico en la literatura se diferencian en la forma en que abordan tales restricciones y las incertidumbres, para volver el problema computacionalmente manejable. Por un lado, están las estrategias deterministas que, fuera de línea, convierten las restricciones probabilísticas en unas nuevas de tipo deterministas, usando la propagación de las incertidumbres a lo largo del horizonte de predicción para ajustar las restricciones duras originales. Por otra parte, las estrategias basadas en escenarios usan la información de las incertidumbres para, en cada instante de muestreo, generar de forma aleatoria un conjunto de posibles evoluciones de éstas a lo largo del horizonte de predicción. De esta manera, convierten las restricciones probabilísticas en un conjunto de restricciones deterministas que deben cumplirse para todos los escenarios generados. Estas estrategias se destacan por su capacidad de incluir en tiempo real información actualizada de las incertidumbres. No obstante, esta ventaja genera inconvenientes como su gasto computacional, el cual aumenta conforme lo hace el número de escenarios y; por otra parte, el efecto no deseado en el problema de optimización, causado por los escenarios con baja probabilidad de ocurrencia, cuando se usa un conjunto de escenarios pequeño. Los retos mencionados anteriormente orientaron esta tesis hacia los enfoques de MPC estocástico basado en escenarios, produciendo tres contribuciones principales. La primera consiste en un estudio comparativo de un algoritmo del grupo determinista con otro del grupo basado en escenarios; se hace un especial énfasis en cómo cada uno de estos aborda las incertidumbres, transforma las restricciones probabilísticas y en la estructura de su OCP, además de señalar sus aspectos más destacados y desafíos. La segunda contribución es una nueva propuesta de algoritmo MPC, el cual se basa en escenarios condicionales, diseñado para sistemas lineales con incertidumbres correlacionadas. Este esquema aprovecha la existencia de tal correlación para convertir un conjunto de escenarios inicial de gran tamaño en un conjunto de escenarios más pequeño con sus probabilidades de ocurrencia, el cual conserva las características del conjunto inicial. El conjunto reducido es usado en un OCP en el que las predicciones de los estados y entradas del sistema son penalizadas de acuerdo con las probabilidades de los escenarios que las componen, dando menor importancia a los escenarios con menores probabilidades de ocurrencia. La tercera contribución consiste en un procedimiento para la implementación del nuevo algoritmo MPC como gestor de la energía en una microrred en la que las previsiones de las energías renovables y las cargas están correlacionadas. / [CA] La gran majoria de processos del món real tenen incerteses inherents, les quals, en ser considerades en el procés de modelatge, es pot obtenir una representació que descriga amb la major precisió possible el comportament del procés real. En la majoria de casos pràctics, es considera que aquestes tenen un comportament estocàstic i les seues descripcions com a distribucions de probabilitats són conegudes. Les estratègies de MPC estocàstic estan desenvolupades per al control de processos amb incerteses de naturalesa estocàstica, on el coneixement de les propietats estadístiques de les incerteses és aprofitat en incloure'l en el plantejament d'un problema de control òptim (OCP). En aquest, i contrari a altres esquemes de MPC, les restriccions dures són relaxades en reformulades com a restriccions de tipus probabilístiques amb la finalitat de reduir el conservadorisme. Això és, es permeten les violacions de les restriccions dures originals, però tals violacions no han d'excedir un nivell de risc permès. La no-convexitat de tals restriccions probabilístiques fan que el problema d'optimització siga computacionalment immanejable, per la qual cosa la majoria de les estratègies de MPC estocàstic en la literatura es diferencien en la forma en què aborden tals restriccions i les incerteses, per a tornar el problema computacionalment manejable. D'una banda, estan les estratègies deterministes que, fora de línia, converteixen les restriccions probabilístiques en unes noves de tipus deterministes, usant la propagació de les incerteses al llarg de l'horitzó de predicció per a ajustar les restriccions dures originals. D'altra banda, les estratègies basades en escenaris usen la informació de les incerteses per a, en cada instant de mostreig, generar de manera aleatòria un conjunt de possibles evolucions d'aquestes al llarg de l'horitzó de predicció. D'aquesta manera, converteixen les restriccions probabilístiques en un conjunt de restriccions deterministes que s'han de complir per a tots els escenaris generats. Aquestes estratègies es destaquen per la seua capacitat d'incloure en temps real informació actualitzada de les incerteses. No obstant això, aquest avantatge genera inconvenients com la seua despesa computacional, el qual augmenta conforme ho fa el nombre d'escenaris i; d'altra banda, l'efecte no desitjat en el problema d'optimització, causat pels escenaris amb baixa probabilitat d'ocurrència, quan s'usa un conjunt d'escenaris xicotet. Els reptes esmentats anteriorment van orientar aquesta tesi cap als enfocaments de MPC estocàstic basat en escenaris, produint tres contribucions principals. La primera consisteix en un estudi comparatiu d'un algorisme del grup determinista amb un altre del grup basat en escenaris; on es fa un especial èmfasi en com cadascun d'aquests aborda les incerteses, transforma les restriccions probabilístiques i en l'estructura del seu problema d'optimització, a més d'assenyalar els seus aspectes més destacats i desafiaments. La segona contribució és una nova proposta d'algorisme MPC, el qual es basa en escenaris condicionals, dissenyat per a sistemes lineals amb incerteses correlacionades. Aquest esquema aprofita l'existència de tal correlació per a convertir un conjunt d'escenaris inicial de gran grandària en un conjunt d'escenaris més xicotet amb les seues probabilitats d'ocurrència, el qual conserva les característiques del conjunt inicial. El conjunt reduït és usat en un OCP en el qual les prediccions dels estats i entrades del sistema són penalitzades d'acord amb les probabilitats dels escenaris que les componen, donant menor importància als escenaris amb menors probabilitats d'ocurrència. La tercera contribució consisteix en un procediment per a la implementació del nou algorisme MPC com a gestor de l'energia en una microxarxa en la qual les previsions de les energies renovables i les càrregues estan correlacionades. / [EN] The vast majority of real-world processes have inherent uncertainties, which, when considered in the modelling process, can provide a representation that most accurately describes the behaviour of the real process. In most practical cases, these are considered to have stochastic behaviour and their descriptions as probability distributions are known. Stochastic model predictive control algorithms are developed to control processes with uncertainties of a stochastic nature, where the knowledge of the statistical properties of the uncertainties is exploited by including it in the optimal control problem (OCP) statement. Contrary to other model predictive control (MPC) schemes, hard constraints are relaxed by reformulating them as probabilistic constraints to reduce conservatism. That is, violations of the original hard constraints are allowed, but such violations must not exceed a permitted level of risk. The non-convexity of such probabilistic constraints renders the optimisation problem computationally unmanageable, thus most stochastic MPC strategies in the literature differ in how they deal with such constraints and uncertainties to turn the problem computationally tractable. On the one hand, there are deterministic strategies that, offline, convert probabilistic constraints into new deterministic ones, using the propagation of uncertainties along the prediction horizon to tighten the original hard constraints. Scenario-based approaches, on the other hand, use the uncertainty information to randomly generate, at each sampling instant, a set of possible evolutions of uncertainties over the prediction horizon. In this fashion, they convert the probabilistic constraints into a set of deterministic constraints that must be fulfilled for all the scenarios generated. These strategies stand out for their ability to include real-time updated uncertainty information. However, this advantage comes with inconveniences such as computational effort, which grows as the number of scenarios does, and the undesired effect on the optimisation problem caused by scenarios with a low probability of occurrence when a small set of scenarios is used. The aforementioned challenges steered this thesis toward stochastic scenario-based MPC approaches, and yielded three main contributions. The first one consists of a comparative study of an algorithm from the deterministic group with another one from the scenario-based group, where a special emphasis is made on how each of them deals with uncertainties, transforms the probabilistic constraints and on the structure of the optimisation problem, as well as pointing out their most outstanding aspects and challenges. The second contribution is a new proposal for a MPC algorithm, which is based on conditional scenarios, developed for linear systems with correlated uncertainties. This scheme exploits the existence of such correlation to convert a large initial set of scenarios into a smaller one with their probabilities of occurrence, which preserves the characteristics of the initial set. The reduced set is used in an OCP in which the predictions of the system states and inputs are penalised according to the probabilities of the scenarios that compose them, giving less importance to the scenarios with lower probabilities of occurrence. The third contribution consists of a procedure for the implementation of the new MPC algorithm as an energy manager in a microgrid in which the forecasts of renewables and loads are correlated. / González Querubín, EA. (2024). Scenario-Based Model Predictive Control for Systems with Correlated Uncertainties [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/203887