Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1981. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Bibliography: leaves 120-124. / by John Nikolaos Tsitsiklis. / M.S.

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.

O problema de controle de estoques com demanda não estacionária e lead-time positivo tem se tornado cada vez mais relevante em virtude da crescente tendência de redução do ciclo de vida dos produtos e internacionalização das cadeias de suprimentos. Embora haja uma solução exata para a minimização do custo esperado da política de estoques para este cenário, baseado no método de programação dinâmica, o custo computacional deste método ainda é considerado elevado. Este trabalho detalha e avalia através de simulação o método exato e duas aproximações para a minimização do custo esperado da política de estoques, em termos do desempenho em custo e eficiência computacional. Os resultados experimentais permitem a análise dos métodos disponíveis. Enquanto a abordagem heurística de Bollapragada e Morton, que utiliza o nivelamento da demanda não estacionária, perde desempenho de custo com o aumento do lead-time, a nova heurística proposta, que aproxima os parâmetros da política ótima por valores limitantes, produz resultados sucessivamente melhores com o aumento do lead-time. / The inventory control problem with nonstationary demand and positive lead-time has become increasingly important due to the growing trend of reduction in product life cycle and internationalization of the supply chain. Although there is an exact solution to the minimization of the expected cost of inventory policy on this environment, through the method of dynamic programming, the computational cost of this method is still considered high. This work details and evaluates through simulation the exact method and two heuristic solutions for the minimization of expected cost of inventory policy, in terms of cost performance and computational efficiency. The experimental results allow the analysis of the available methods. While the Bollapragada and Morton heuristic approach, which levels the non-stationary demand, decreases the cost performance when lead-time is increased, the new heuristic proposed, that approximates the optimal policy parameters by limiting values, successively produces better results with increasing lead-times.

Thesis (Sc.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Bibliography: leaves 898-903. / by Howard Jay Chizeck. / Sc.D.

We present solution methodologies for vehicle routing problems (VRPs) with stochastic demand, with a specific focus on the vehicle routing problem with stochastic demand (VRPSD) and the vehicle routing problem with stochastic demand and duration limits (VRPSDL). The VRPSD and the VRPSDL are fundamental problems underlying many operational challenges in the fields of logistics and supply chain management. We model the VRPSD and the VRPSDL as large-scale Markov decision processes. We develop cyclic-order neighborhoods, a general methodology for solving a broad class of VRPs, and use this technique to obtain static, fixed route policies for the VRPSD. We develop pre-decision, post-decision, and hybrid rollout policies for approximate dynamic programming (ADP). These policies lay a methodological foundation for solving large-scale sequential decision problems and provide a framework for developing dynamic routing policies. Our dynamic rollout policies for the VRPSDL significantly improve upon a method frequently implemented in practice. We also identify circumstances in which our rollout policies appear to offer little or no benefit compared to this benchmark. These observations can guide managerial decision making regarding when the use of our procedures is justifiable. We also demonstrate that our methodology lends itself to real-time implementation, thereby providing a mechanism to make high-quality, dynamic routing decisions for large-scale operations. Finally, we consider a more traditional ADP approach to the VRPSDL by developing a parameterized linear function to approximate the value functions corresponding to our problem formulation. We estimate parameters via a simulation-based algorithm and show that initializing parameter values via our rollout policies leads to significant improvements. However, we conclude that additional research is required to develop a parametric ADP methodology comparable or superior to our rollout policies.

Traffic signal systems serve as one of the most powerful control tools in improving the efficiency of surface transportation travel. Traffic operations on arterial roads are particularly complex because of traffic interruptions caused by signalized intersections along the corridor. This dissertation research presents a systematic framework of integrated traffic control in an attempt to break down the complexities into several simpler sub-problems such as pattern recognition, environment-mobility relationships and multi-objective optimization for multi-criterial signal timing design. The overall goal of this dissertation is to develop signal timing plans, including a day plan schedule, cycle length parameters, splits and offsets, which are suitable for real traffic conditions with consideration of multi-criterial performance of the surface transportation system. To this end, the specific objectives are to: (1) identify appropriate time-of-day breakpoints and intervals to accommodate traffic pattern variations for day plan schedule of signal timing; (2) explore the relationship between environmental outcomes (e.g., emissions) from emission estimators and mobility measures (e.g., delay and stops) for different types of intersections; (3) optimize signal timing parameters for multi-criteria objectives (e.g., minimizing vehicular delay, number of stops, marginal costs of emissions and total costs), with the comparison of performance metrics for different objectives, at the intersection level; (4) optimize arterial offsets for different objectives at the arterial level and compare the performance metrics of different objectives to recommend suitable objectives for integrated multi-criteria signal timing design in arterial traffic operations. An extensive review of the literature, which covers existing tools, traffic patterns, traffic control with environmental concerns, and related optimization methods, shows that both opportunities and challenges have emerged for multi-criteria traffic signal timing design. These opportunities include large quantities of traffic condition data collected by system detectors or non-intrusive data collection platforms as well as powerful tools for microscopic traffic modeling and instantaneous emission estimation. The challenge is how to effectively deal with these big data, either from field collection or detailed simulation, and provide useful information for decision makers in practice. Methodologically, there's a tradeoff between the accuracy of objective function values and the computational efficiency of simulation and optimization. To address this need, in this dissertation, traffic signal timing design that systematically enables the use of integrated data and models are investigated and analyzed in the four steps/studies. The technology of identifying time-of-day breakpoints in the first study shows a mathematical way to classify dynamic traffic patterns by understanding dynamic traffic features and instabilities at a macroscopic level on arterials. Given the limitations of using built-in emissions modules within current traffic simulation and signal optimization tools, the metamodeling-based approach presented in the second study makes a methodological contribution. The findings of the second study on environment-mobility relationships set up the base for extensive application of two-stage optimization in the third and fourth studies for sustainable traffic operations and management. The comparison of outputs from an advanced estimator with those from the current tool also addresses improving the emissions module for more accurate analysis (e.g., benefit-cost analysis) in practical signal retiming projects. The third study shows that there are tradeoffs between minimizing delay and minimizing marginal costs of emissions. When total cost (including cost of delay, fuel consumption and emissions) is set as a single objective function, that objective clears the way for relatively reliable results for all the aspects. In the fourth study, the improvements in marginal cost of emissions and total cost by dynamic programming procedure are obvious, which indicates the effectiveness of using total link cost as an objective at the corridor level. In summary, this dissertation advocates a sustainable traffic control system by simultaneously considering travel time, fuel consumption and emissions. The outcomes of this integrated multi-criteria signal timing design can be easily implemented by traffic operators in their daily life of retiming signal timing.

<p>Research in the last few decades has revealed the great capacity of the RNA molecule. RNA, which previously was assumed to play a main role only as an intermediate in the translation of genes to proteins, is today known to play many important roles in the cell in addition to that as a messenger RNA and transfer RNA, including the ability to catalyze reactions and gene regulations at various levels.</p><p>This thesis investigates several computational aspects of RNA. We will discuss identification of novel RNAs and RNAs that are known to exist in related species, RNA secondary structure prediction, as well as more general tools for analyzing, visualizing and classifying RNA sequences.</p><p>We present two benchmark studies concerning RNA identification, both de novo identification/characterization of single RNA sequences and homology search methods.</p><p>We develope a novel algorithm for analysis of the RNA folding landscape that is based on the nearest neighbor energy model adopted in many secondary structure prediction programs. We implement this algorithm, which computes structural neighbors of a given RNA secondary structure, in the program RNAbor, which is accessible on a web server.</p><p>Furthermore, we combine a mutual information based structure prediction algorithm with a sequence logo visualization to create a novel visualization tool for analyzing an RNA alignment and identifying covarying sites.</p><p>Finally, we present extensions to sequence logos for the purpose of tRNA identity analysis. We introduce function logos, which display features that distinguish functional subclasses within a large set of structurally related sequences, as well as the inverse logos, which display underrepresented features. For the purpose of comparing tRNA identity elements between different taxa we introduce two contrasting logos, the information difference and the Kullback-Leibler divergence difference logos.</p>

In this paper, we minimize the holding cost of the safety stock in the supply chain subject to linear constraints on the service times between the nodes of the network. In the problem, the objective function is concave as we assume the demand to be bounded by a concave function. The optimal solutions of the problem belong to the set of extreme points of the polyhedron, specified by the constraints of the problem. We first characterize the extreme points for the two-layer networks and then provide bounds to use in a branch and bound algorithm. / Singapore-MIT Alliance (SMA)

The purpose of this research is to develop a model and solution methodology for selecting and scheduling timely and cost-effective maintenance, rehabilitation, and reconstruction activities (M & R) for each pavement section in a highway network and allocating the funding levels through a finite multi-period horizon within the constraints imposed by budget availability in each period, frequency availability of activities, and specified minimum pavement quality requirements. M & R is defined as a chronological sequence of reconstruction, rehabilitation, and major/minor maintenance, including a "do nothing" activity. A procedure is developed for selecting an M & R activity for each pavement section in each period of a specified extended planning horizon. Each activity in the sequence consumes a known amount of capital and generates a known amount of effectiveness measured in pavement quality. The effectiveness of an activity is the expected value of the overall gains in pavement quality rating due to the activity performed on a highway network over an analysis period. It is assumed that the unused portion of the budget for one period can be carried over to subsequent periods. Dynamic Programming (DP) and Branch-and-Bound (B-and-B) approaches are combined to produce a hybrid algorithm for solving the problem under consideratioin. The algorithm is essentially a DP approach in the sense that the problem is divided into smaller subproblems corresponding to each single period problem. However, the idea of fathoming partial solutions that could not lead to an optimal solution is incorporated within the algorithm to reduce storage and computational requirements in the DP frame using the B-and-B approach. The imbedded-state approach is used to reduce a multi-dimensional DP to a one-dimensional DP. For bounding at each stage, the problem is relaxed in a Lagrangean fashion so that it separates into longest-path network model subproblems. The values of the Lagrangean multipliers are found by a subgradient optimization method, while the Ford-Bellman network algorithm is employed at each iteration of the subgradient optimization procedure to solve the longest-path network problem as well as to obtain an improved lower and upper bound. If the gap between lower and upper bound is sufficiently small, then we may choose to accept the best known solutions as being sufficiently close to optimal and terminate the algorithm rather than continue to the final stage.