Title: Stochastic Dynamic Programming Problems: Theory and Applications Author: Gabriel Lendel Department: Department of Probability and Mathematical Statistics Supervisor: Ing. Karel Sladký CSc. Supervisor's e-mail address: sladky@utia.cas.cz Abstract: In the present work we study Markov decision processes which provide a mathematical framework for modeling decision-making in situations where outcomes are partly random and partly under the control of a decision maker. We study iterative procedures for finding policy that is optimal or nearly optimal with respect to the selec- ted criteria. Specifically, we mainly examine the task of finding a policy that is optimal with respect to the total expected discounted reward or the average expected reward for discrete or continuous systems. In the work we study policy iteration algorithms and aproximative value iteration algorithms. We give numerical analysis of specific problems. Keywords: Stochastic dynamic programming, Markov decision process, policy ite- ration, value iteration

O planejamento da operação energética em sistemas hidrotérmicos de potência com um único reservatório tem como objetivo determinar a participação de usinas hidrelétricas e térmicas de forma a garantir o suprimento de energia demandada ao menor custo operacional possível, dentro de restrições físicas e técnicas do modelo. Alguns fatores tornam a solução deste problema bastante complexa destacando a não linearidade e a não separabilidade temporal aditiva. O objetivo deste trabalho é apresentar uma nova abordagem com tratamento agregado das afluências, descrevendo uma nova caracterização das distribuições de probabilidades e um novo modelo para a programação dinâmica estocástica markoviana. Nesse novo modelo da programação dinâmica estocástica markoviana, agregações plurimensais de vazões são utilizadas como entrada em um modelo de programação dinâmica estocástica markoviana modificado para discretizações temporais plurimensais. A nova abordagem proposta foi simulada em diferentes usinas hidrelétricas brasileiras localizadas em diferentes regiões geográficas e sob diferentes regimes hidrológicos. Os resultados das simulações feitas com a utilização deste novo modelo são apresentados e comparados ao modelo de programação dinâmica estocástica markoviana mensal, atualmente utilizado no setor elétrico brasileiro, com economia de custos relativas superiores a 10% em alguns casos. / The energetic operation planning on hydrothermal power systems with a single reservoir aims to determine the participation of hydroelectric power plants and thermal power plants to guaranty supply of energy demanded with the smallest possible cost, under physical and technical model boundaries. Some points became the solution of this problem complex, highlighting the non linearity and the additive non time separability. The objective of this paper is show the new approach with aggregated inflows, describing a new probability distributions featuring and a new model for the markovian stochastic dynamic programming. On this new model of markovian stochastic dynamic programming, multi monthly inflow aggregations are used as input in a model of markovian stochastic dynamic programming modified for multi months discretizations. The new approach proposed was simulated on differents Brazilian hydroelectric power plants located on different regions and under different hydrologic regime. The results of simulations using this new model are presented and compared to the model of monthly markovian dynamic programming, nowadays used on the Brazilian electrical sector, with relatives economic savings up to 10% in some cases.

Cette thèse propose des définitions mathématiques des concepts de résilience et de vulnérabilité dans le cadre des systèmes dynamiques stochastiques contrôlés, et en particulier celui de la viabilité stochastique en temps discret. Elle s’appuie sur les travaux antérieurs définissant la résilience dans le cadre de la viabilité pour des dynamiques déterministes. Les définitions proposées font l’hypothèse qu’il est possible de distinguer des aléas usuels, inclus dans la dynamique, et des événements extrêmes ou surprenants dont on étudie spécifiquement l’impact. La viabilité stochastique et la fiabilité ne mettent en jeu que le premier type d’aléa, et s’intéressent à l’évaluation de la probabilité de sortir d’un sous-ensemble de l’espace d’état dans lequel les propriétés d’intérêt du système sont satisfaites. La viabilité stochastique apparaît ainsi comme une branche de la fiabilité. Un objet central en est le noyau de viabilité stochastique, qui regroupe les états contrôlables pour que leur probabilité de garder les propriétés sur un horizon temporel défini soit supérieure à un seuil donné. Nous proposons de définir la résilience comme la probabilité de revenir dans le noyau de viabilité stochastique après un événement extrême ou surprenant. Nous utilisons la programmation dynamique stochastique pour maximiser la probabilité d’être viable ainsi que pour optimiser la probabilité de résilience à un horizon temporel donné. Nous proposons de définir ensuite la vulnérabilité à partir d’une fonction de dommage définie sur toutes les trajectoires possibles du système. La distribution des trajectoires définit donc une distribution de probabilité des dommages et nous définissons la vulnérabilité comme une statistique sur cette distribution. Cette définition s’applique aux deux types d’aléas définis précédemment. D’une part, en considérant les aléas du premier type, nous définissons des ensembles tels que la vulnérabilité soit inférieure à un seuil, ce qui généralise la notion de noyau de viabilité stochastique. D’autre part, après un aléa du deuxième type, la vulnérabilité fournit des indicateurs qui aident à décrire les trajectoires de retour (en considérant que seul l’aléa de premier type intervient). Des indicateurs de vulnérabilité lié à un coût ou au franchissement d’un seuil peuvent être minimisés par la programmation dynamique stochastique. Nous illustrons les concepts et outils développés dans la thèse en les appliquant aux indicateurs pré-existants de fiabilité et de vulnérabilité, utilisés pour évaluer la performance d’un système d’approvisionnement en eau. En particulier, nous proposons un algorithme de programmation dynamique stochastique pour minimiser un critère qui combine des critères de coût et de sortie de l’ensemble de contraintes. Les concepts sont ensuite articulés pour décrire la performance d’un réservoir. / This thesis proposes mathematical definitions of the resilience and vulnerability concepts, in the framework of stochastic controlled dynamical system, and particularly that of discrete time stochastic viability theory. It relies on previous works defining resilience in the framework of deterministic viability theory. The proposed definitions stem from the hypothesis that it is possible to distinguish usual uncertainty, included in the dynamics, from extreme or surprising events. Stochastic viability and reliability only deal with the first kind of uncertainty, and both evaluate the probability of exiting a subset of the state space in which the system’s properties are verified. Stochastic viability thus appears to be a branch of reliability theory. One of its central objects is the stochastic viability kernel, which contains all the states that are controllable so their probability of keeping the properties over a given time horizon is greater than a threshold value. We propose to define resilience as the probability of getting back to the stochastic viability kernel after an extreme or surprising event. We use stochastic dynamic programming to maximize both the probability of being viable and the probability of resilience at a given time horizon. We propose to then define vulnerability from a harm function defined on every possible trajectory of the system. The trajectories’ probability distribution implies that of the harm values and we define vulnerability as a statistic over this latter distribution. This definition is applicable with both the aforementioned uncertainty sources. On one hand, considering usual uncertainty, we define sets such that vulnerability is below a threshold, which generalizes the notion of stochastic viability kernel. On the other hand, after an extreme or surprising event, vulnerability proposes indicators to describe recovery trajectories (assuming that only usual uncertainty comes into play then). Vulnerability indicators related to a cost or to the crossing of a threshold can be minimized thanks to stochastic dynamic programming. We illustrate the concepts and tools developed in the thesis through an application to preexisting indicators of reliability and vulnerability that are used to evaluate the performance of a water supply system. We focus on proposing a stochastic dynamic programming algorithm to minimize a criterion that combines criteria of cost and of exit from the constraint set. The concepts are then articulated to describe the performance of a reservoir.

O planejamento da operação energética em sistemas hidrotérmicos de potência com um único reservatório tem como objetivo determinar a participação de usinas hidrelétricas e térmicas de forma a garantir o suprimento de energia demandada ao menor custo operacional possível, dentro de restrições físicas e técnicas do modelo. Alguns fatores tornam a solução deste problema bastante complexa destacando a não linearidade e a não separabilidade temporal aditiva. O objetivo deste trabalho é apresentar uma nova abordagem com tratamento agregado das afluências, descrevendo uma nova caracterização das distribuições de probabilidades e um novo modelo para a programação dinâmica estocástica markoviana. Nesse novo modelo da programação dinâmica estocástica markoviana, agregações plurimensais de vazões são utilizadas como entrada em um modelo de programação dinâmica estocástica markoviana modificado para discretizações temporais plurimensais. A nova abordagem proposta foi simulada em diferentes usinas hidrelétricas brasileiras localizadas em diferentes regiões geográficas e sob diferentes regimes hidrológicos. Os resultados das simulações feitas com a utilização deste novo modelo são apresentados e comparados ao modelo de programação dinâmica estocástica markoviana mensal, atualmente utilizado no setor elétrico brasileiro, com economia de custos relativas superiores a 10% em alguns casos. / The energetic operation planning on hydrothermal power systems with a single reservoir aims to determine the participation of hydroelectric power plants and thermal power plants to guaranty supply of energy demanded with the smallest possible cost, under physical and technical model boundaries. Some points became the solution of this problem complex, highlighting the non linearity and the additive non time separability. The objective of this paper is show the new approach with aggregated inflows, describing a new probability distributions featuring and a new model for the markovian stochastic dynamic programming. On this new model of markovian stochastic dynamic programming, multi monthly inflow aggregations are used as input in a model of markovian stochastic dynamic programming modified for multi months discretizations. The new approach proposed was simulated on differents Brazilian hydroelectric power plants located on different regions and under different hydrologic regime. The results of simulations using this new model are presented and compared to the model of monthly markovian dynamic programming, nowadays used on the Brazilian electrical sector, with relatives economic savings up to 10% in some cases.

A Web-server farm is a specialized facility designed specifically for housing Web servers catering to one or more Internet facing Web sites. In this dissertation, stochastic dynamic programming technique is used to obtain the optimal admission control policy with different classes of customers, and stochastic uid- ow models are used to compute the performance measures in the network. The two types of network traffic considered in this research are streaming (guaranteed bandwidth per connection) and elastic (shares available bandwidth equally among connections). We first obtain the optimal admission control policy using stochastic dynamic programming, in which, based on the number of requests of each type being served, a decision is made whether to allow or deny service to an incoming request. In this subproblem, we consider a xed bandwidth capacity server, which allocates the requested bandwidth to the streaming requests and divides all of the remaining bandwidth equally among all of the elastic requests. The performance metric of interest in this case will be the blocking probability of streaming traffic, which will be computed in order to be able to provide Quality of Service (QoS) guarantees. Next, we obtain bounds on the expected waiting time in the system for elastic requests that enter the system. This will be done at the server level in such a way that the total available bandwidth for the requests is constant. Trace data will be converted to an ON-OFF source and fluid- flow models will be used for this analysis. The results are compared with both the mean waiting time obtained by simulating real data, and the expected waiting time obtained using traditional queueing models. Finally, we consider the network of servers and routers within the Web farm where data from servers flows and merges before getting transmitted to the requesting users via the Internet. We compute the waiting time of the elastic requests at intermediate and edge nodes by obtaining the distribution of the out ow of the upstream node. This out ow distribution is obtained by using a methodology based on minimizing the deviations from the constituent in flows. This analysis also helps us to compute waiting times at different bandwidth capacities, and hence obtain a suitable bandwidth to promise or satisfy the QoS guarantees. This research helps in obtaining performance measures for different traffic classes at a Web-server farm so as to be able to promise or provide QoS guarantees; while at the same time helping in utilizing the resources of the server farms efficiently, thereby reducing the operational costs and increasing energy savings.

This research introduces a general approach for integrating a probabilistic model of the changes in the committed orders with an analytical model of production and inventory planning under multi-period Quantity Flexibility contracts. We study a decentralized structure where a capacitated manufacturer, capable of subcontracting, serves multiple contract buyers who actually perform forecasts on a rolling horizon basis. We model the evolution of buyers&#039 / commitments as a multiplicative forecast evolution process accommodating contract revision limits. A finite Markovian approximation to this sophisticated evolution model is introduced for facilitating the associated complex probability modeling. We implement computational dynamic programming and introduce an effective approach for reducing state-space dimensionality building upon our forecast evolution structure. Computational investigation demonstrates how the manufacturer benefits from the existence of order commitments and subcontracting option by analyzing the interplay of decisions.

This thesis covers a utility optimizing model designed and calibrated for agents of the Swedish economy. The main ingredient providing for this specific country is the modeling of the pension accumulation and pension benefits, which closely mimics the Swedish system. This characteristic is important since it measures one of the only two diversities between genders, that is, the income. The second characteristic is the survival probability. Except for these differences in national statistics, men and women are equal. The reminding model parameters are realistically set estimates from the surrounding economy. When using the model, firstly a baseline agent representing the entire labor force is under the microscope for evaluating the model itself. Next, one representative woman and one representative man from the private and public sectors respectively, composes a set of four samples for investigation of heterogeneity in optimality. The optimum level of consumption and risk-proportion of liquid wealth are solved by maximizing an Epstein-Zin utility function using the method of dynamic programming. The results suggests that both genders benefit from adapting the customized solutions to the problem.

Intégrée dans la chaîne décisionnelle de la Supply Chain à un niveau tactique, la Planification de Production est un process clé qui permet de répondre au mieux aux besoins selon les ressources de l’entreprise. Un des défis du domaine est la gestion des incertitudes prévisionnelles, ayant des conséquences importantes sur des indicateurs clés comme le taux de service ou les coûts. Pour y faire face, des méthodes améliorant la flexibilité des processus sont mais en place, comme le contexte de travail en Plan Glissant. Cependant, en actualisant fréquemment les données, la stabilité du système se retrouve dégradée. Ainsi, malgré les gains issus de la gestion des incertitudes, ce cadre crée une complexité dynamique à gérer. Ce travail traite de cette complexité issue de l’actualisation des prévisions pour la planification de production en plan glissant. Plus particulièrement, la question traitée ici concerne l’optimisation du plan de production, en considérant u n système mono-produit monoétage. Une modélisation mathématique générique est tout d’abord développée pour construire un modèle d’optimisation théorique du problème. Ensuite, une procédure de résolution optimale est développée en utilisant le cadre d’optimisation dynamique stochastique. Ce modèle est appliquée à des cas concrets pour lesquels l’optimalité des solutions calculées est prouvée analytiquement grâce à un raisonnement inductif basé sur des séquences de calcul d’espérances mathématiques. Des analyses numériques finalement conduites mettent en exergue les performances de la méthode développée, ses limites, et sa sensibilité vis-à-vis de l’environnement industriel. / Production Planning, as part of tactical operations integrated into the Supply Chain process, is a key procedure allowing decisioners to balance demand and production resources. One of its most challenging issues is to handle uncertainties, especially the ones coming from the Forecasted Demand. In order to manage indicators at stake, such as service level and costs, best practices increasing flexibility in the process are implemented, as Rolling-Plan Framework. However, it creates instability since the updates procedures make the data set on change constantly. Consequently, although the gain in terms of flexibility is non-negligible for the uncertainties management, it generates on the other hand dynamics complexity. We study in this work how to deal this dynamics complexity generated by updates of the Forecasted Demand made in a Rolling-Plan Framework of a Production Planning Process. In particular, the question to which it answers is how to optimize the Production Plan in such a context. This issue is tackled considering a single item single level production system. A general mathematical model in the context of our study is built to be exploitable for analytical optimization. A theoretical optimization framework is designed, and a specific solutions computation framework using stochastic dynamic programming is developed. We apply it in some precise study cases in order to compute optimal solutions and get some valuable analytical results thanks to a dynamic computation process. The optimality of the solutions is proven through an inductive reasoning based on expectations computation. Solutions are finally implemented and calculated numerically with simulations in some particular numerical examples. Analyses and sensitivity studies are performed, highlighting the performances of our optimization method.

A feasibility study of an irrigation development proposal should include an analysis of the effects of water supply conditions on the degree to which development objectives are expected to be realised. A method of making this analysis was developed based on procedures for solving two problems. These were; (a) optimally allocating a property's available supply of water among competing crops, and, (b) optimally controlling an open channel distribution system to meet temporally and spatially varying water demand. The procedure developed for solving (a) was applied. A stochastic dynamic programming procedure was developed to optimally schedule the irrigation of a single crop, subject to constraints on the timing of water availability and total application depth. A second procedure was developed, employing a constrained differential dynamic programming algorithm, for determining optimal irrigation schedules for use with variable application depth systems, and when several crops compete for an intra-seasonally limited supply of water. This procedure was called, as frequently as water supply conditions allowed, to provide short-term irrigation schedules in a computer simulation of the optimal irrigation of several crops. An application system model was included in these procedures to transform a crop water-use production function into the required irrigation water-use production function. This transformation was a function of the application device type and the mean application depth. From an analysis of the on-property effects of water supply conditions, it was concluded that in order to achieve high economic and irrigation efficiencies, water supply conditions must be sufficiently flexible to allow the application system operator to vary the mean application depth but not necessarily the time periods of water availability. Additionally, irrigation scheduling procedures which seek economically optimum strategies offer the potential to achieve a maximum level of net benefit at levels of water availability significantly lower than has previously been used for design purposes.

Abstract The negative impact of invasive plant species on biodiversity and ecosystem functions, such as productivity and nutrient cycling has been deemed a global epidemic. To address this worldwide concern, information is needed on how the invasion process happens and how to control an existing invasion. The main aim of the research presented in this thesis was to develop a better understanding of the interacting role different mechanisms play in facilitating invasion and then link this understanding to the design of more effective control strategies. This aim is significant because traditional weed control strategies are not working. The estimated cost of controlling weeds in Australia is $1.4 billion per year in agricultural landscapes. Despite this substantial investment, invasive weed species are estimated to continue to cost the agricultural industry $2.2 billion per year in loss of yield. Current control strategies tend to focus on killing or removing an invasive plant species directly with the application of herbicides and/or mechanical removal. These strategies have proven ineffectual because the plant communities that assemble after management often remain dominated by the same invader or another. In this thesis, I use a combination of empirical and modelling techniques to investigate how disturbance regimes and competitive interactions between invasive plants and native plants can be manipulated to improve the efficacy of restoration efforts. To do this, I use the model scenario of the invasion of Eragrostis curvula (African lovegrass), an invasive grass species introduced into Australia in the early 1900s from South Africa. This species has now spread into every Australian state and territory (chapter 2). I specifically focus on two mechanisms: (1) disturbance, i.e. cattle grazing, and (2) competitive interactions. In chapter 3, I examine connections between dominance and competitive differences among African lovegrass and several functionally similar native grass species in a pasture community. To test the displacement hypothesis, I used a glasshouse competition trial to investigate interactions between African lovegrass and two non-persisting native grass species (Themeda australis and Bothriochloa decipiens) with manipulations of resources, neighbour density, and establishment order. To test the partitioning hypothesis, I compared in situ water use patterns among African lovegrass and two coexisting native grass species (Aristida calycina and Aristida personata) based on the assumption that water is the most limiting resource in this system. The key finding of this chapter is that competition can have important, but contingent, impacts on dominance. Competitive differences appear to partially contribute to abundance patterns after establishment, but may be relatively unimportant during the establishment phase where disturbance appears more critical. In chapter 4, I provide evidence that the identification of mechanisms that led to an invasion, while crucial for the development of effective preventative measures and understanding the invasion process, may not be necessary for the design of more effective control strategies. To examine the effects of different control strategies on African lovegrass and the resultant community, I established a large factorial field-trial with a split-plot design. I manipulated grazing, soil nutrient levels and the presence of the invader. The most common control strategy (removing the causal disturbance and killing the invasive grass), based implicitly on traditional equilibrium models, was not an effective option for restoring a desirable native community. Instead, this strategy led to the dominance of a secondary invader. The most effective control strategy was based on alternative stable states models and involved maintaining grazing, and increasing the palatability of the invader with fertilizers. The key finding of this chapter is that novel approaches for control, which consider the dynamics of the invader-dominated system, are needed. In chapter 5, I investigate the benefits of explicitly incorporating actions that manipulate disturbance (natural or imposed) into control efforts. To do this, I first developed a process model that described the dynamics of an invader whose establishment is preferentially favoured by disturbance. I then couched this model in a decision theory framework, a stochastic dynamic program, and applied a case-study of another invasive plant species, Mimosa pigra (a perennial legume shrub and pan-tropical weed). The key finding of this chapter is that strategies should not only focus on existing invader-dominated sites, but should also protect sites occupied by native species from disturbances that facilitate invasion. The research discussed in this thesis makes three key contributions to a better understanding of the invasion process and the design of more effective control strategies: 1) the search for one key mechanism is not sufficient because multiple mechanisms can interact or shift in importance to facilitate different stages of invasion, 2) a novel approach is needed to restore a more desirable native community because the dynamics of the invader-dominated system can differ from the historical native community, and 3) control efforts should be broadened in focus to include protection of the integrity of native communities from disturbances that facilitate invasion.