M.Sc (Computer Science.) / This dissertation details the implementation of SNAP, a stochastic network analysis package, as the basis of an in-house computer configuration planning facility. The work was performed at Head Office, Gold Fields of South Africa Limited, Johannesburg, South Africa (GFSA) during the period April 1980 to December 1981. SNAP was developed by the Institute of Applied Computer Science at the University of Stellenbosch, Stellenbosch, South Africa. The implementation of SNAP at GFSA signalled the first in-house SNAP facility, and the first SNAP implementation on an ICL computer (although implementation had been in progress at another ICL site since 1979). Although this dissertation is very specific in nature, it is intended to provide an insight into the methodology employed in planning and implementing an in-house configuration planning facility. An overview of multiclass queueing network models and the SNAP package is provided, although no attempt is made to explain the stochastic theory of queueing networks in any detail. Attention is thereafter focussed on the various phases of the project. Problems were encountered in monitoring performance data, and these are looked at in some depth. The question of workload characterization and the difficulties of producing a satisfactory GFSA classification strategy are then presented. The model design, calibration and validation stages are explained using the GFSA model. Thereafter, use of the model for prediction purposes is illustrated by means of a number of examples. Finally, tne memory management model is discussed - main memory does not form part of the SNAP model and has to be dealt with as a separate issue.

No description available.

This thesis compares actual and perceived travel times and presents a model for predicting traffic flows when there is a network disruption. The goal of this research is to demonstrate the necessity of accounting for possible differences in travel time perception and actual travel times, and also to show trends in how the route choices change based on the transformation of the perceived travel times. A pilot test was done to determine actual travel time perceptions, and the results provided the foundation for the tests presented in this thesis and the model framework. The model is separated into three phases: equilibrium assignment, link travel time transform, and logit assignment. The transform of the link travel times is best represented by an inverse cumulative Normal distribution, and the corresponding values provide quantifiable measure of the severity of a traffic network disruption. The methodology is presented and applied to two test networks to demonstrate the resulting route choice patterns. Both networks are tested for three severity levels and three levels of demand. / text

abstract: Short-notice disasters such as hurricanes involve uncertainties in many facets, from the time of its occurrence to its impacts’ magnitude. Failure to incorporate these uncertainties can affect the effectiveness of the emergency responses. In the case of a hurricane event, uncertainties and corresponding impacts during a storm event can quickly cascade. Over the past decades, various storm forecast models have been developed to predict the storm uncertainties; however, access to the usage of these models is limited. Hence, as the first part of this research, a data-driven simulation model is developed with aim to generate spatial-temporal storm predicted hazards for each possible hurricane track modeled. The simulation model identifies a means to represent uncertainty in storm’s movement and its associated potential hazards in the form of probabilistic scenarios tree where each branch is associated with scenario-level storm track and weather profile. Storm hazards, such as strong winds, torrential rain, and storm surges, can inflict significant damage on the road network and affect the population’s ability to move during the storm event. A cascading network failure algorithm is introduced in the second part of the research. The algorithm takes the scenario-level storm hazards to predict uncertainties in mobility states over the storm event. In the third part of the research, a methodology is proposed to generate a sequence of actions that simultaneously solve the evacuation flow scheduling and suggested routes which minimize the total flow time, or the makespan, for the evacuation process from origins to destinations in the resulting stochastic time-dependent network. The methodology is implemented for the 2017 Hurricane Irma case study to recommend an evacuation policy for Manatee County, FL. The results are compared with evacuation plans for assumed scenarios; the research suggests that evacuation recommendations that are based on single scenarios reduce the effectiveness of the evacuation procedure. The overall contributions of the research presented here are new methodologies to: (1) predict and visualize the spatial-temporal impacts of an oncoming storm event, (2) predict uncertainties in the impacts to transportation infrastructure and mobility, and (3) determine the quickest evacuation schedule and routes under the uncertainties within the resulting stochastic transportation networks. / Dissertation/Thesis / Doctoral Dissertation Industrial Engineering 2020

abstract: This dissertation advances the capability of water infrastructure utilities to anticipate and adapt to vulnerabilities in their systems from temperature increase and interdependencies with other infrastructure systems. Impact assessment models of increased heat and interdependencies were developed which incorporate probability, spatial, temporal, and operational information. Key findings from the models are that with increased heat the increased likelihood of water quality non-compliances is particularly concerning, the anticipated increases in different hardware components generate different levels of concern starting with iron pipes, then pumps, and then PVC pipes, the effects of temperature increase on hardware components and on service losses are non-linear due to spatial criticality of components, and that modeling spatial and operational complexity helps to identify potential pathways of failure propagation between infrastructure systems. Exploring different parameters of the models allowed for comparison of institutional strategies. Key findings are that either preventative maintenance or repair strategies can completely offset additional outages from increased temperatures though-- improved repair times reduce overall duration of outages more than preventative maintenance, and that coordinated strategies across utilities could be effective for mitigating vulnerability. / Dissertation/Thesis / Doctoral Dissertation Civil, Environmental and Sustainable Engineering 2019

This research presents a bi-level stochastic network interdiction model on an attack graph to enable a risk-averse resource constrained cyber network defender to optimally deploy security countermeasures to protect against attackers having an uncertain budget. This risk-averse conditional-value-at-risk model minimizes a weighted sum of the expected maximum loss over all scenarios and the expected maximum loss from the most damaging attack scenarios. We develop an exact algorithm to solve our model as well as several acceleration techniques to improve the computational efficiency. Computational experiments demonstrate that the application of all the acceleration techniques reduces the average computation time of the basic algorithm by 71% for 100-node graphs. Using metrics called mean-risk value of stochastic solution and value of risk-aversion, numerical results suggest that our stochastic risk-averse model significantly outperforms deterministic and risk-neutral models when 1) the distribution of attacker budget is heavy-right-tailed and 2) the defender is highly risk-averse.

Congestion is a world-wide problem in transportation. One major reason is random interruptions. The traffic network is inherently stochastic, and strong dependencies exist among traffic quantities, e.g., travel time, traffic speed, link volume. Information in stochastic networks can help with adaptive routing in terms of minimizing expected travel time or disutility. Routing in such networks is different from that in deterministic networks or when stochastic dependencies are not taken into account. This dissertation addresses the optimal routing problems, including the optimal a priori path problem and the optimal adaptive routing problem with different information scenarios, in stochastic and time-dependent networks with explicit consideration of the correlations between link travel time random variables. There are a number of studies in the literature addressing the optimal routing problems, but most of them ignore the correlations between link travel times. The consideration of the correlations makes the problem studied in this dissertation difficult, both conceptually and computationally. The optimal path finding problem in such networks is different from that in stochastic and time-dependent networks with no consideration of the correlations. This dissertation firstly provides an empirical study of the correlations between random link travel times and also verifies the importance of the consideration of the spatial and temporal correlations in estimating trip travel time and its reliability. It then shows that Bellman's principle of optimality or non-dominance is not valid due to the time-dependency and the correlations. A new property termed purity is introduced and an exact label-correcting algorithm is designed to solve the problem. With the fast advance of telecommunication technologies, real-time traffic information will soon become an integral part of travelers' route choice decision making. The study of optimal adaptive routing problems is thus timely and of great value. This dissertation studies the problems with a wide variety of information scenarios, including delayed global information, real-time local information, pre-trip global information, no online information, and trajectory information. It is shown that, for the first four partial information scenarios, Bellman's principle of optimality does not hold. A heuristic algorithm is developed and employed based on a set of necessary conditions for optimality. The same algorithm is showed to be exact for the perfect online information scenario. For optimal adaptive routing problem with trajectory information, this dissertation proves that, if the routing policy is defined in a similar way to other four information scenarios, i.e., the trajectory information is included in the state variable, Bellman's principle of optimality is valid. However, this definition results in a prohibitively large number of the states and the computation can hardly be carried out. The dissertation provides a recursive definition for the trajectory-adaptive routing policy, for which the information is not included in the state variable. In this way, the number of states is small, but Bellman's principle of optimality or non-dominance is invalid for a similar reason as in the optimal path problem. Again purity is introduced to the trajectory-adaptive routing policy and an exact algorithm is designed based on the concept of decreasing order of time.

We describe a stochastic network interdiction problem in which an interdictor, subject to limited resources, installs radiation detectors at border checkpoints in a transportation network in order to minimize the probability that a smuggler of nuclear material can traverse the residual network undetected. The problems are stochastic because the smuggler's origin-destination pair, the mass and type of material being smuggled, and the level of shielding are known only through a probability distribution when the detectors are installed. We consider three variants of the problem. The first is a Stackelberg game which assumes that the smuggler chooses a maximum-reliability path through the network with full knowledge of detector locations. The second is a Cournot game in which the interdictor and the smuggler act simultaneously. The third is a "hybrid" game in which only a subset of detector locations is revealed to the smuggler. In the Stackelberg setting, the problem is NP-complete even if the interdictor can only install detectors at border checkpoints of a single country. However, we can compute wait-and-see bounds in polynomial time if the interdictor can only install detectors at border checkpoints of the origin and destination countries. We describe mixed-integer programming formulations and customized branch-and-bound algorithms which exploit this fact, and provide computational results which show that these specialized approaches are substantially faster than more straightforward integer-programming implementations. We also present some special properties of the single-country case and a complexity landscape for this family of problems. The Cournot variant of the problem is potentially challenging as the interdictor must place a probability distribution over an exponentially-sized set of feasible detector deployments. We use the equivalence of optimization and separation to show that the problem is polynomially solvable in the single-country case if the detectors have unit installation costs. We present a row-generation algorithm and a version of the weighted majority algorithm to solve such instances. We use an exact-penalty result to formulate a model in which some detectors are visible to the smuggler and others are not. This may be appropriate to model "decoy" detectors and detector upgrades. / text

Transportvorgänge in und von Zellen sind von herausragender Bedeutung für das Überleben des Organismus. Muskeln müssen sich kontrahieren können, Chromosomen während der Mitose an entgegengesetzte Enden der Zelle bewegt und Organellen, das sind von Membranen umschlossene Kompartimente, entlang molekularer Schienen transportiert werden. <br /> Molekulare Motoren sind Proteine, deren Hauptaufgabe es ist, andere Moleküle zu bewegen. Dazu wandeln sie die bei der ATP-Hydrolyse freiwerdende chemische Energie in mechanische Arbeit um. Die Motoren des Zellskeletts gehören zu den drei Superfamilien Myosin, Kinesin und Dynein. Ihre Schienen sind Filamente des Zellskeletts, Actin und die Microtubuli. <br /> In dieser Arbeit werden stochastische Modelle untersucht, welche dazu dienen, die Fortbewegung dieser linearen molekularen Motoren zu beschreiben. Die Skala, auf der wir die Bewegung betrachten, reicht von einzelnen Schritten eines Motorproteins bis in den Bereich der gerichteten Bewegung entlang eines Filaments. Ein Einzelschritt überbrückt je nach Protein etwa 10 nm und wird in ungefähr 10 ms zurückgelegt. Unsere Modelle umfassen M Zustände oder Konformationen, die der Motor annehmen kann, während er sich entlang einer eindimensionalen Schiene bewegt. An K Orten dieser Schiene sind Übergänge zwischen den Zuständen möglich. Die Geschwindigkeit des Proteins lässt sich in Abhängigkeit von den vertikalen Übergangsraten zwischen den einzelnen Zuständen analytisch bestimmen. Wir berechnen diese Geschwindigkeit für Systeme mit bis zu vier Zuständen und Orten und können weiterhin eine Reihe von Regeln ableiten, die uns einschätzen helfen, wie sich ein beliebiges vorgegebenes System verhalten wird. <br /> Darüber hinaus betrachten wir entkoppelte Subsysteme, also einen oder mehrere Zustände, die keine Verbindung zum übrigen System haben. Mit einer bestimmten Wahrscheinlichkeit kann ein Motor einen Zyklus von Konformationen durchlaufen, mit einer anderen Wahrscheinlichkeit einen davon unabhängigen anderen. <br /> Aktive Elemente werden in realen Transportvorgängen durch Motorproteine nicht auf die Übergänge zwischen den Zuständen beschränkt sein. In verzerrten Netzwerken oder ausgehend von der diskreten Mastergleichung des Systems können auch horizontale Raten spezifiziert werden und müssen weiterhin nicht mehr die Bedingungen der detaillierten Balance erfüllen. Damit ergeben sich eindeutige, komplette Pfade durch das jeweilige Netzwerk und Regeln für die Abhängigkeit des Gesamtstroms von allen Raten des Systems. Außerdem betrachten wir die zeitliche Entwicklung für vorgegebene Anfangsverteilungen. <br /> Bei Enzymreaktionen gibt es die Idee des Hauptpfades, dem diese bevorzugt folgen. Wir bestimmen optimale Pfade und den maximalen Fluss durch vorgegebene Netzwerke. <br /> Um darüber hinaus die Geschwindigkeit des Motors in Abhängigkeit von seinem Treibstoff ATP angeben zu können, betrachten wir mögliche Reaktionskinetiken, die den Zusammenhang zwischen den unbalancierten Übergangsraten und der ATP-Konzentration bestimmen. Je nach Typ der Reaktionskinetik und Anzahl unbalancierter Raten ergeben sich qualitativ unterschiedliche Verläufe der Geschwindigkeitskurven in Abhängigkeit von der ATP-Konzentration. <br /> Die molekularen Wechselwirkungspotentiale, die der Motor entlang seiner Schiene erfährt, sind unbekannt.Wir vergleichen unterschiedliche einfache Potentiale und die Auswirkungen auf die Transportkoeffizienten, die sich durch die Lokalisation der vertikalen Übergänge im Netzwerkmodell im Vergleich zu anderen Ansätzen ergeben. / Transport processes in and of cells are of major importance for the survival of the organism. Muscles have to be able to contract, chromosomes have to be moved to opposing ends of the cell during mitosis, and organelles, which are compartments enclosed by membranes, have to be transported along molecular tracks.<br /> Molecular motors are proteins whose main task is moving other molecules.For that purpose they transform the chemical energy released in the hydrolysis of ATP into mechanical work. The motors of the cytoskeleton belong to the three super families myosin, kinesin and dynein. Their tracks are filaments of the cytoskeleton, namely actin and the microtubuli. <br /> Here, we examine stochastic models which are used for describing the movements of these linear molecular motors. The scale of the movements comprises the regime of single steps of a motor protein up to the directed walk along a filament. A single step bridges around 10 nm, depending on the protein, and takes about 10 ms, if there is enough ATP available. Our models comprise M states or conformations the motor can attain during its movement along a one-dimensional track. At K locations along the track transitions between the states are possible. The velocity of the protein depending on the transition rates between the single states can be determined analytically. We calculate this velocity for systems of up to four states and locations and are able to derive a number of rules which are helpful in estimating the behaviour of an arbitrary given system.<br /> Beyond that we have a look at decoupled subsystems, i.e., one or a couple of states which have no connection to the remaining system. With a certain probability a motor undergoes a cycle of conformational changes, with another probability an independent other cycle. <br /> Active elements in real transport processes by molecular motors will not be limited to the transitions between the states. In distorted networks or starting from the discrete Master equation of the system, it is possible to specify horizontal rates, too, which furthermore no longer have to fulfill the conditions of detailed balance. Doing so, we obtain unique, complete paths through the respective network and rules for the dependence of the total current on all the rates of the system. Besides, we view the time evolutions for given initial distributions. <br /> In enzymatic reactions there is the idea of a main pathway these reactions follow preferably. We determine optimal paths and the maximal flow for given networks. <br /> In order to specify the dependence of the motor's velocity on its fuel ATP, we have a look at possible reaction kinetics determining the connection between unbalanced transitions rates and ATP-concentration. Depending on the type of reaction kinetics and the number of unbalanced rates, we obtain qualitatively different curves connecting the velocity to the ATP-concentration. <br /> The molecular interaction potentials the motor experiences on its way along its track are unknown. We compare different simple potentials and the effects the localization of the vertical rates in the network model has on the transport coefficients in comparison to other models.

This thesis explores stochastic modeling and Bayesian inference strategies in the context of the following three problems: 1) Modeling the complex interactions between and within molecules; 2) Extracting information from stepwise signals that are commonly found in biophysical experiments; 3) Improving the computational efficiency of a non-parametric Bayesian inference algorithm. Chapter 1 studies the data from a recent single-molecule biophysical experiment on enzyme kinetics. Using a stochastic network model, we analyze the autocorrelation of experimental fluorescence intensity and the autocorrelation of enzymatic reaction times. This chapter shows that the stochastic network model is capable of explaining the experimental data in depth and further explains why the enzyme molecules behave fundamentally differently from what the classical model predicts. The modern knowledge on the molecular kinetics is often learned through the information extracted from stepwise signals in experiments utilizing fluorescence spectroscopy. Chapter 2 proposes a new Bayesian method to estimate the change-points in stepwise signals. This approach utilizes marginal likelihood as the tool of inference. This chapter illustrates the impact of the choice of prior on the estimator and provides guidelines for setting the prior. Based on the results of simulation study, this method outperforms several existing change-points estimators under certain settings. Furthermore, DNA array CGH data and single molecule data are analyzed with this approach. Chapter 3 focuses on the optional Polya tree, a newly established non-parametric Bayesian approach (Wong and Li 2010). While the existing study shows that the optional Polya tree is promising in analyzing high dimensional data, its applications are hindered by the high computational costs. A heuristic algorithm is proposed in this chapter, with an attempt to speed up the optional Polya tree inference. This study demonstrates that the new algorithm can reduce the running time significantly with a negligible loss of precision. / Statistics