To see the other types of publications on this topic, follow the link: Dynamic Programming: models.
Dissertations / Theses on the topic 'Dynamic Programming: models'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Dynamic Programming: models.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Lévesque, Moren. "Models of entrepreneurial decisions, a dynamic programming approach." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp02/NQ34577.pdf.
Full text
2
Elliott, Jennifer T. "Territorial defense and mate attraction in isolated and social white-breasted nuthatches (Sitta carolinensis): tests of stochastic dynamic programming models /." Connect to this title online, 2005. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu.
Full textAbstract:
Thesis (Ph. D.)--Ohio State University, 2005.Title from first page of PDF file. Document formatted into pages; contains xxi, 200 p.; also includes graphics. Includes bibliographical references (p. 194-200). Available online via OhioLINK's ETD Center.
3
Luxhoj, James T. "A dynamic programming approach to the multi-stream replacement problem." Diss., Virginia Polytechnic Institute and State University, 1986. http://hdl.handle.net/10919/49829.
Full text
4
Estalrich-Lopez, Juan. "Short-term operation of surface reservoirs within long-term goals." Diss., The University of Arizona, 1989. http://hdl.handle.net/10150/184854.
Full textAbstract:
A stochastic dynamic programming model (called P.B.S.D.P.) based on the consideration of peak discharge and time between peaks as two stochastic variables has been used to model and to solve a reservoir operation problem. This conceptualization of the physical reality allows to solve, in this order, the tactical and strategic operation of surface reservoirs. This P.B.S.D.P. model has been applied to the Sau reservoir in the Northeastern corner of Spain. The results showed a significant improvement over the currently used operation procedure, yielding values of yearly average electricity production that are somewhat under 6% of what could have been the maximum electricity production.
5
Toriello, Alejandro. "Time decomposition of multi-period supply chain models." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/42704.
Full textAbstract:
Many supply chain problems involve discrete decisions in a dynamic environment. The inventory routing problem is an example that combines the dynamic control of inventory at various facilities in a supply chain with the discrete routing decisions of a fleet of vehicles that moves product between the facilities.
We study these problems modeled as mixed-integer programs and propose a time decomposition based on approximate inventory valuation. We generate the approximate value function with an algorithm that combines data fitting, discrete optimization and dynamic programming methodology. Our framework allows the user to specify a class of piecewise linear, concave functions from which the algorithm chooses the value function. The use of piecewise linear concave functions is motivated by intuition, theory and practice. Intuitively, concavity reflects the notion that inventory is marginally more valuable the closer one is to a stock-out. Theoretically, piecewise linear concave functions have certain structural properties that also hold for finite mixed-integer program value functions. (Whether the same properties hold in the infinite case is an open question, to our knowledge.) Practically, piecewise linear concave functions are easily embedded in the objective function of a maximization mixed-integer or linear program, with only a few additional auxiliary continuous variables. We evaluate the solutions generated by our value functions in a case study using maritime inventory routing instances inspired by the petrochemical industry.
The thesis also includes two other contributions. First, we review various data fitting optimization models related to piecewise linear concave functions, and introduce new mixed-integer programming formulations for some cases. The formulations may be of independent interest, with applications in engineering, mixed-integer non-linear programming, and other areas. Second, we study a discounted, infinite-horizon version of the canonical single-item lot-sizing problem and characterize its value function, proving that it inherits all properties of interest from its finite counterpart. We then compare its optimal policies to our algorithm's solutions as a proof of concept.
6
Machado, Rui Mário da Silva. "Massivel y parallel declarative computational models." Doctoral thesis, Universidade de Évora, 2013. http://hdl.handle.net/10174/12063.
Full textAbstract:
Current computer archictectures are parallel, with an increasing number of processors. Parallel programming is an error-prone task and declarative models such as those based on constraints relieve the programmer from some of its difficult aspects, because they abstract control away. In this work we study and develop techniques for declarative computational models based on constraints using GPI, aiming at large scale parallel execution. The main contributions of this work are: A GPI implementation of a scalable dynamic load balancing scheme based on work
stealing, suitable for tree shaped computations and effective for systems with thousands of threads. A parallel constraint solver, MaCS, implemented to take advantage of the GPI programming model. Experimental evaluation shows very good scalability results on systems with hundreds of cores. A GPI parallel version of the Adaptive Search algorithm, including different variants. The study on different problems advances the understanding of scalability issues known to exist with large numbers of cores; ### SUMÁRIO: Actualmente as arquitecturas de computadores são paralelas, com um crescente número de processadores. A programação paralela é uma tarefa propensa a erros e modelos declarativos baseados em restrições
aliviam o programador de aspectos difíceis dado que abstraem o controlo. Neste trabalho estudamos e desenvolvemos técnicas para modelos de computação declarativos baseados em restrições usando o GPI, uma ferramenta e modelo de programação recente. O Objectivo é a execução paralela em larga escala. As contribuições deste trabalho são as seguintes: a implementação de um esquema dinâmico para balanceamento da computação baseado no GPI. O esquema é adequado para computações em árvores e efectiva em sistemas compostos por milhares de unidades de computação. Uma abordagem à resolução paralela de restrições denominadas de MaCS, que tira partido do modelo de programação do GPI. A Avaliação experimental revelou boa escalabilidade num sistema com centenas de processadores. Uma versão paralela do algoritmo Adaptive Search baseada no GPI, que inclui diferentes variantes. O estudo de diversos problemas aumenta a compreensão de aspectos relacionados com a escalabilidade e presentes na execução deste tipo de algoritmos num grande número de processadores.
7
Jiao, Yue. "Mathematical models for control of probabilistic Boolean networks." Click to view the E-thesis via HKUTO, 2008. http://sunzi.lib.hku.hk/hkuto/record/B41508634.
Full text
8
Chitic, Stefan-Gabriel. "Middleware and programming models for multi-robot systems." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEI018/document.
Full textAbstract:
Malgré de nombreuses années de travail en robotique, il existe toujours un manque d’architecture logicielle et de middleware stables pour les systèmes multi-robot. Un intergiciel robotique devrait être conçu pour faire abstraction de l’architecture matérielle de bas niveau, faciliter la communication et l’intégration de nouveaux logiciels. Cette thèse se concentre sur le middleware pour systèmes multi-robot et sur la façon dont nous pouvons améliorer les frameworks existantes dans un contexte multi-robot en ajoutant des services de coordination multi-robot, des outils de développement et de déploiement massif. Nous nous attendons à ce que les robots soient de plus en plus utiles car ils peuvent tirer profit des données provenant d’autres périphériques externes dans leur prise de décision au lieu de simplement réagir à leur environnement local (capteurs, robots coopérant dans une flotte, etc.). Cette thèse évalue d’abord l’un des intergiciels les plus récents pour robot(s) mobile(s), Robot operating system (ROS), suivi par la suite d’un état de l’art sur les middlewares couramment utilisés en robotique. Basé sur les conclusions, nous proposons une contribution originale dans le contexte multi-robots, appelé SDfR (Service discovery for Robots), un mécanisme de découverte des services pour les robots. L’objectif principal est de proposer un mécanisme permettant aux robots de garder une trace des pairs accessibles à l’intérieur d’une flotte tout en utilisant une infrastructure ad-hoc. A cause de la mobilité des robots, les techniques classiques de configuration de réseau pair à pair ne conviennent pas. SDfR est un protocole hautement dynamique, adaptatif et évolutif adapté du protocole SSDP (Simple Service Discovery Protocol). Nous conduisons un ensemble d’expériences, en utilisant une flotte de robots Turtlebot, pour mesurer et montrer que le surdébit de SDfR est limité. La dernière partie de la thèse se concentre sur un modèle de programmation basé sur un automate temporisé. Ce type de programmation a l’avantage d’avoir un modèle qui peut être vérifié et simulé avant de déployer l’application sur de vrais robots. Afin d’enrichir et de faciliter le développement d’applications robotiques, un nouveau modèle de programmation basé sur des automates à états temporisés est proposé, appelé ROSMDB (Robot Operating system Model Driven Behaviour). Il fournit une vérification de modèle lors de la phase de développement et lors de l’exécution. Cette contribution est composée de plusieurs composants : une interface graphique pour créer des modèles basés sur un automate temporisé, un vérificateur de modèle intégré basé sur UPPAAL et un générateur de squelette de code. Enfin, nous avons effectué deux expériences : une avec une flotte de drones Parrot et l’autre avec des Turtlebots afin d’illustre le modèle proposé et sa capacité à vérifier les propriétésDespite many years of work in robotics, there is still a lack of established software architecture and middleware for multi-robot systems. A robotic middleware should be designed to abstract the low-level hardware architecture, facilitate communication and integration of new software. This PhD thesis is focusing on middleware for multi-robot system and how we can improve existing frameworks for fleet purposes by adding multi-robot coordination services, development and massive deployment tools. We expect robots to be increasingly useful as they can take advantage of data pushed from other external devices in their decision making instead of just reacting to their local environment (sensors, cooperating robots in a fleet, etc). This thesis first evaluates one of the most recent middleware for mobile robot(s), Robot operating system (ROS) and continues with a state of the art about the commonly used middlewares in robotics. Based on the conclusions, we propose an original contribution in the multi-robot context, called SDfR (Service discovery for Robots), a service discovery mechanism for Robots. The main goal is to propose a mechanism that allows highly mobile robots to keep track of the reachable peers inside a fleet while using an ad-hoc infrastructure. Another objective is to propose a network configuration negotiation protocol. Due to the mobility of robots, classical peer to peer network configuration techniques are not suitable. SDfR is a highly dynamic, adaptive and scalable protocol adapted from Simple Service Discovery Protocol (SSDP). We conduced a set of experiments, using a fleet of Turtlebot robots, to measure and show that the overhead of SDfR is limited. The last part of the thesis focuses on programming model based on timed automata. This type of programming has the benefits of having a model that can be verified and simulated before deploying the application on real robots. In order to enrich and facilitate the development of robotic applications, a new programming model based on timed automata state machines is proposed, called ROSMDB (Robot Operating system Model Driven Behaviour). It provides model checking at development phase and at runtime. This contribution is composed of several components: a graphical interface to create models based on timed automata, an integrated model checker based on UPPAAL and a code skeleton generator. Moreover, a ROS specific framework is proposed to verify the correctness of the execution of the models and to trigger alerts. Finally, we conduct two experiments: one with a fleet of Parrot drones and second with Turtlebots in order to illustrates the proposed model and its ability to check properties
9
Uong, Hoang. "The application of the ordered list method and the dynamic programming to the unit commitment." PDXScholar, 1989. https://pdxscholar.library.pdx.edu/open_access_etds/3948.
Full text
10
Jiao, Yue, and 焦月. "Mathematical models for control of probabilistic Boolean networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2008. http://hub.hku.hk/bib/B41508634.
Full text
11
Cheng, Gang. "Analyzing and Solving Non-Linear Stochastic Dynamic Models on Non-Periodic Discrete Time Domains." TopSCHOLAR®, 2013. http://digitalcommons.wku.edu/theses/1236.
Full textAbstract:
Stochastic dynamic programming is a recursive method for solving sequential or multistage decision problems. It helps economists and mathematicians construct and solve a huge variety of sequential decision making problems in stochastic cases. Research on stochastic dynamic programming is important and meaningful because stochastic dynamic programming reflects the behavior of the decision maker without risk aversion; i.e., decision making under uncertainty. In the solution process, it is extremely difficult to represent the existing or future state precisely since uncertainty is a state of having limited knowledge. Indeed, compared to the deterministic case, which is decision making under certainty, the stochastic case is more realistic and gives more accurate results because the majority of problems in reality inevitably have many unknown parameters. In addition, time scale calculus theory is applicable to any field in which a dynamic process can be described with discrete or continuous models. Many stochastic dynamic models are discrete or continuous, so the results of time scale calculus are directly applicable to them as well. The aim of this thesis is to introduce a general form of a stochastic dynamic sequence problem on complex discrete time domains and to find the optimal sequence which maximizes the sequence problem.
12
Johnson, Thomas Alex. "Integrating models and simulations of continuous dynamic system behavior into SysML." Thesis, Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24768.
Full text
13
McGarity, Michael Computer Science & Engineering Faculty of Engineering UNSW. "Heterogeneous representations for reinforcement learning control of dynamic systems." Awarded by:University of New South Wales. School of Computer Science and Engineering, 2004. http://handle.unsw.edu.au/1959.4/19350.
Full textAbstract:
Intelligent agents are designed to interact with, and learn about, their environment so that they can act purposefully towards a goal. One class of problems encountered in building such agents is learning how to respond to dynamic systems with a continuous state space. The goals of this dissertation are to develop a framework for understanding the behaviour of partitioned dynamic systems with continuous underlying state and to translate this framework into algorithms which adaptively form a partition of the continuous space such that the partitioned system is more easily learned and controlled, and such that the control law may be easily explained in intuitive ways. Currently, algorithms which learn a control policy for partitioned continuous state space systems treat the partitioned system as an approximation to a Markov chain. I give conditions for the partitioned system to be a Markov chain, a semi-Markov process and a new class of system, a weak-semi-Markov process. The weak-semi-Markov model is shown to model partitioned dynamic systems with greater economy than other surveyed models. The behaviour of a partitioned state space system in the area around the region boundaries is also considered. I use the theory of sliding surfaces, and some heuristic arguments to recommend region boundary shape and position. The concept of 'staying on the boundary' then becomes a robust and relatively easy subgoal within the control algorithm. The concept of 'reaching the sliding surface' as a subgoal is used as the basis for an intuitive explanation of the learnt controller. I present an algorithm based on this concept which explains the behaviour of a learnt controller in ways not previously available to a machine learning algorithms. Finally, the Markov Property and the theory of Sliding Mode Control are used as the basis of a class of recursive algorithms. These algorithms adaptively find a partition, and simultaneously use this partition in conjunction with one of five reinforcement learning algorithms to find a control policy based on that partition. This technique is shown to work very well in learning, controlling and explaining a variety of physical systems, from a monorail to a container crane.
14
Turhan, Nezihe. "Deterministic and Stochastic Bellman's Optimality Principles on Isolated Time Domains and Their Applications in Finance." TopSCHOLAR®, 2011. http://digitalcommons.wku.edu/theses/1045.
Full textAbstract:
The concept of dynamic programming was originally used in late 1949, mostly during the 1950s, by Richard Bellman to describe decision making problems. By 1952, he refined this to the modern meaning, referring specifically to nesting smaller decision problems inside larger decisions. Also, the Bellman equation, one of the basic concepts in dynamic programming, is named after him. Dynamic programming has become an important argument which was used in various fields; such as, economics, finance, bioinformatics, aerospace, information theory, etc. Since Richard Bellman's invention of dynamic programming, economists and mathematicians have formulated and solved a huge variety of sequential decision making problems both in deterministic and stochastic cases; either finite or infinite time horizon. This thesis is comprised of five chapters where the major objective is to study both deterministic and stochastic dynamic programming models in finance. In the first chapter, we give a brief history of dynamic programming and we introduce the essentials of theory. Unlike economists, who have analyzed the dynamic programming on discrete, that is, periodic and continuous time domains, we claim that trading is not a reasonably periodic or continuous act. Therefore, it is more accurate to demonstrate the dynamic programming on non-periodic time domains. In the second chapter we introduce time scales calculus. Moreover, since it is more realistic to analyze a decision maker’s behavior without risk aversion, we give basics of Stochastic Calculus in this chapter. After we introduce the necessary background, in the third chapter we construct the deterministic dynamic sequence problem on isolated time scales. Then we derive the corresponding Bellman equation for the sequence problem. We analyze the relation between solutions of the sequence problem and the Bellman equation through the principle of optimality. We give an example of the deterministic model in finance with all details of calculations by using guessing method, and we prove uniqueness and existence of the solution by using the Contraction Mapping Theorem. In the fourth chapter, we define the stochastic dynamic sequence problem on isolated time scales. Then we derive the corresponding stochastic Bellman equation. As in the deterministic case, we give an example in finance with the distributions of solutions.
15
Ramirez, Jose A. "Optimal and Simulation-Based Approximate Dynamic Programming Approaches for the Control of Re-Entrant Line Manufacturing Models." University of Cincinnati / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1282329260.
Full text
16
Haerian, Laila. "Airline Revenue Management: models for capacity control of a single leg and a network of flights." Columbus, Ohio : Ohio State University, 2007. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1181839192.
Full text
17
El-Hadad, Kamel Abdelsalam Mahmoud. "Expert systems and simulation : an investigation of an expert system to facilitate the development and use of system dynamic simulation models." Thesis, University of Kent, 1991. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.279602.
Full text
18
Babcock, Elizabeth A. "Dynamic programming models of fishermen's choice of target species assemblage in the U.S. west coast groundfish trawl fishery /." Thesis, Connect to this title online; UW restricted, 1998. http://hdl.handle.net/1773/5340.
Full text
19
Wong, Wee Chin. "Estimation and control of jump stochastic systems." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/31775.
Full textAbstract:
Thesis (Ph.D)--Chemical Engineering, Georgia Institute of Technology, 2010.Committee Chair: Jay H. Lee; Committee Member: Alexander Gray; Committee Member: Erik Verriest; Committee Member: Magnus Egerstedt; Committee Member: Martha Grover; Committee Member: Matthew Realff. Part of the SMARTech Electronic Thesis and Dissertation Collection.
20
Yang, Ruiduo. "Dynamic programming with multiple candidates and its applications to sign language and hand gesture recognition." [Tampa, Fla.] : University of South Florida, 2008. http://purl.fcla.edu/usf/dc/et/SFE0002310.
Full text
21
Tsener, Inna. "Numerical methods for analyzing nonstationary dynamic economic models and their applications." Doctoral thesis, Universidad de Alicante, 2015. http://hdl.handle.net/10045/50216.
Full text
22
Baik, Hojong. "Development of Optimization and Simulation Models for the Analysis of Airfield Operations." Diss., Virginia Tech, 2000. http://hdl.handle.net/10919/28162.
Full textAbstract:
This research is concerned with the modeling and development of algorithmic approaches for solving airport operational problems that arise in Air Traffic Control (ATC) systems within the terminal area at hub airports. Specifically, the problems addressed include the Aircraft Sequencing Problem (ASP) for runway operations, the Network Assignment Problem (NAP) for taxiway operations, and a simulation model for the evaluation of current or proposed ATC system in detail.
For the ASP, we develop a mathematical model and apply the Reformulation-Linearization-Technique (RLT) of Sherali and Adams to construct an enhanced tightened version of the proposed model. Since ASP is NP-Hard and in fact, it is a variation of the well-known Traveling Salesman Problem with time-windows, sub-optimal solutions are usually derived to accommodate the real-time constraints of ATC systems. Nevertheless, we exhibit a significant advancement in this challenging class of problem. Also for the purpose of solving relatively large sized problems in practice, we develop and test suitable heuristic procedures.
For the NAP, we propose a quasi-dynamic assignment scheme which is based on the incremental assignment technique. This quasi-dynamic assignment method assumes that the current aircraft route is influenced only by the previous aircraft assigned to the network. This simplified assumption obviates the need for iterative rerouting procedures to reach a pure equilibrium state which might not be achievable in practical taxiway operations. To evaluate the overall system, we develop a microscopic simulation model. The simulation model is designed to have the capability for reproducing not only the dynamic behavior of aircraft, but also incorporates communication activities between controllers and pilots. These activities are critical in ATC operations, and in some instances, might limit the capacity of the facility.
Finally, using the developed simulation model named Virginia Tech Airport Simulation Model (VTASM) in concert with ASP and NAP, we compare the overall efficiencies of several control strategies, including that of the existing control system as well as of the proposed advanced control system.Ph. D.
23
Elliott, Jennifer Theresa. "Territorial defense and mate attraction in isolated and social white-breasted nuthatches (Sitta carolinensis): tests of stochastic dynamic programming models." The Ohio State University, 2005. http://rave.ohiolink.edu/etdc/view?acc_num=osu1110207825.
Full text
24
Ullah, Ikram. "Probabilistic Models for Species Tree Inference and Orthology Analysis." Doctoral thesis, KTH, Beräkningsbiologi, CB, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-168146.
Full textAbstract:
A phylogenetic tree is used to model gene evolution and species evolution using molecular sequence data. For artifactual and biological reasons, a gene tree may differ from a species tree, a phenomenon known as gene tree-species tree incongruence. Assuming the presence of one or more evolutionary events, e.g., gene duplication, gene loss, and lateral gene transfer (LGT), the incongruence may be explained using a reconciliation of a gene tree inside a species tree. Such information has biological utilities, e.g., inference of orthologous relationship between genes. In this thesis, we present probabilistic models and methods for orthology analysis and species tree inference, while accounting for evolutionary factors such as gene duplication, gene loss, and sequence evolution. Furthermore, we use a probabilistic LGT-aware model for inferring gene trees having temporal information for duplication and LGT events. In the first project, we present a Bayesian method, called DLRSOrthology, for estimating orthology probabilities using the DLRS model: a probabilistic model integrating gene evolution, a relaxed molecular clock for substitution rates, and sequence evolution. We devise a dynamic programming algorithm for efficiently summing orthology probabilities over all reconciliations of a gene tree inside a species tree. Furthermore, we present heuristics based on receiver operating characteristics (ROC) curve to estimate suitable thresholds for deciding orthology events. Our method, as demonstrated by synthetic and biological results, outperforms existing probabilistic approaches in accuracy and is robust to incomplete taxon sampling artifacts. In the second project, we present a probabilistic method, based on a mixture model, for species tree inference. The method employs a two-phase approach, where in the first phase, a structural expectation maximization algorithm, based on a mixture model, is used to reconstruct a maximum likelihood set of candidate species trees. In the second phase, in order to select the best species tree, each of the candidate species tree is evaluated using PrIME-DLRS: a method based on the DLRS model. The method is accurate, efficient, and scalable when compared to a recent probabilistic species tree inference method called PHYLDOG. We observe that, in most cases, the analysis constituted only by the first phase may also be used for selecting the target species tree, yielding a fast and accurate method for larger datasets. Finally, we devise a probabilistic method based on the DLTRS model: an extension of the DLRS model to include LGT events, for sampling reconciliations of a gene tree inside a species tree. The method enables us to estimate gene trees having temporal information for duplication and LGT events. To the best of our knowledge, this is the first probabilistic method that takes gene sequence data directly into account for sampling reconciliations that contains information about LGT events. Based on the synthetic data analysis, we believe that the method has the potential to identify LGT highways.QC 20150529
25
Liu, Pengyu. "Extracting Rules from Trained Machine Learning Models with Applications in Bioinformatics." Doctoral thesis, Kyoto University, 2021. http://hdl.handle.net/2433/264678.
Full textAbstract:
京都大学新制・課程博士
博士(情報学)
甲第23397号
情博第766号
新制||情||131(附属図書館)
京都大学大学院情報学研究科知能情報学専攻
(主査)教授 阿久津 達也, 教授 山本 章博, 教授 鹿島 久嗣
学位規則第4条第1項該当
Doctor of Informatics
Kyoto University
DFAM
26
Grimsman, David R. "The Asynchronous t-Step Approximation for Scheduling Batch Flow Systems." BYU ScholarsArchive, 2016. https://scholarsarchive.byu.edu/etd/5957.
Full textAbstract:
Heap models in the max-plus algebra are interesting dynamical systems that can be used to model a variety of tetris-like systems, such as batch flow shops for manufacturing models. Each heap in the model can be identified with a single product to manufacture. The objective is to manufacture a group of products in such an order so as to minimize the total manufacturing time. Because this scheduling problem reduces to a variation of the Traveling Salesman Problem (known to be NP-complete), the optimal solution is computationally infeasible for many real-world systems. Thus, a feasible approximation method is needed. This work builds on and expands the existing heap model in order to more effectively solve the scheduling problems. Specifically, this work:1. Further characterizes the admissible products to these systems.2. Further characterizes sets of admissible products. 3. Presents a novel algorithm, the asynchronous $t$-step approximation, to approximate these systems.4. Proves error bounds for the system approximation, and show why these error bounds are better than the existing approximation.
27
González, Barrameda José Andrés. "Novel Application Models and Efficient Algorithms for Offloading to Clouds." Thesis, Université d'Ottawa / University of Ottawa, 2017. http://hdl.handle.net/10393/36469.
Full textAbstract:
The application offloading problem for Mobile Cloud Computing aims at improving the mobile user experience by leveraging the resources of the cloud. The execution of the mobile application is offloaded to the cloud, saving energy at the mobile device or speeding up the execution of the application. We improve the accuracy and performance of application offloading solutions in three main directions. First, we propose a novel fine-grained application model that supports complex module dependencies such as sequential, conditional and parallel module executions. The model also allows for multiple offloading decisions that are tailored towards the current application, network, or user contexts. As a result, the model is more precise in capturing the structure of the application and supports more complex offloading solutions. Second, we propose three cost models, namely, average-based, statistics-based and interval-based cost models, defined for the proposed application model. The average-based approach models each module cost by the expected cost value, and the expected cost of the entire application is estimated considering each of the three module dependencies. The novel statistics-based cost model employs Cumulative Distribution Function (CDFs) to represent the costs of the modules and of the mobile application, which is estimated considering the cost and dependencies of the modules. This cost model opens the doors for new statistics-based optimization functions and constraints whereas the state of the art only support optimizations based on the average running cost of the application. Furthermore, this cost model can be used to perform statistical analysis of the performance of the application in different scenarios such as varying network data rates. The last cost model, the interval-based, represents the module costs via intervals in order to addresses the cost uncertainty while having lower requirements and computational complexity than the statistics-based model. The cost of the application is estimated as an expected maximum cost via a linear optimization function. Finally, we present offloading decision algorithms for each cost model. For the average-based model, we present a fast optimal dynamic programming algorithm. For the statistics-based model, we present another fast optimal dynamic programming algorithm for the scenario where the optimization function meets specific properties. Finally, for the interval-based cost model, we present a robust formulation that solves a linear number of linear optimization problems. Our evaluations verify the accuracy of the models and show higher cost savings for our solutions when compared to the state of the art.
28
Zhang, Yang. "Advances in LTL load plan design." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/34712.
Full textAbstract:
A load plan specifies how freight is routed through a linehaul terminal network operated by a less-than-truckload (LTL) carrier. Determining the design of the load plan is critical to effective operations of such carriers. This dissertation makes contributions in modeling and algorithm design for three problems in LTL load plan design: (1) Refined execution cost estimation. Existing load plan design models use approximations that ignore important facts such as the nonlinearity of transportation costs with respect to the number of trailers, and empty travel beyond what is required for trailer balance that results from driver rules. We develop models that more accurately capture key operations of LTL carriers and produce accurate operational execution costs estimates; (2) Dynamic load planning. Load plans are traditionally revised infrequently by LTL carriers due to the difficulty of solving the associated optimization problem. Technological advances have now enabled carriers to consider daily load plan updates. We develop technologies that efficiently and effectively adjust a nominal load plan for a given day based on the actual freight to be served by the carrier. We present an integer programming based local search procedure, and a greedy randomized adaptive search heuristic; and (3) Stochastic load plan design. Load plan design models commonly represent origin-destination freight volumes using average demands, which do not describe freight volume fluctuations. We investigate load plan design models that explicitly utilize information on freight volume uncertainty and design load plans that most cost-effectively deal with varying freight volumes and lead to the lowest expected cost. We present a Sample Average Approximation approach and a variant of the method for solving the stochastic integer programming formulations.
29
Calmon, Andre du Pin. "Variação do controle como fonte de incerteza." [s.n.], 2009. http://repositorio.unicamp.br/jspui/handle/REPOSIP/259270.
Full textAbstract:
Orientador: João Bosco Ribeiro do ValDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação
Made available in DSpace on 2018-08-14T00:07:24Z (GMT). No. of bitstreams: 1 Calmon_AndreduPin_M.pdf: 862345 bytes, checksum: 122780715dca28ac7fa3199aa0586e7c (MD5) Previous issue date: 2009
Resumo: Este trabalho apresenta a caracterização teórica e a estratégia de controle para sistemas estocásticos em tempo discreto onde a variação da ação de controle aumenta a incerteza sobre o estado (sistemas VCAI). Este tipo de sistema possui várias aplicações práticas, como em problemas de política monetária, medicina e, de forma geral, em problemas onde um modelo dinâmico completo do sistema é complexo demais para ser conhecido. Utilizando ferramentas da análise de funções não suaves, mostra-se para um sistema VCAI multidimensional que a convexidade é uma invariante da função valor da Programação Dinâmica quando o custo por estágio é convexo. Esta estratégia indica a existência de uma região no espaço de estados onde a ação ótima de controle é de não variação (denominada região de não-variação), estando de acordo com a natureza cautelosa do controle de sistemas subdeterminados. Adicionalmente, estudou-se algoritmos para a obtenção da política ótima de controle para sistemas VCAI, com ênfase no caso mono-entrada avaliado através de uma função custo quadrática. Finalmente, os resultados obtidos foram aplicados no problema da condução da política monetária pelo Banco Central.
Abstract: This dissertation presents a theoretical framework and the control strategy for discrete-time stochastic systems for which the control variations increase state uncertainty (CVIU systems). This type of system model can be useful in many practical situations, such as in monetary policy problems, medicine and biology, and, in general, in problems for which a complete dynamic model is too complex to be feasible. The optimal control strategy for a multidimensional CVIU system associated with a convex cost functional is devised using dynamic programming and tools from nonsmooth analysis. Furthermore, this strategy points to a region in the state space in which the optimal action is of no variation (the region of no variation), as expected from the cautionary nature of controlling underdetermined systems. Numerical strategies for obtaining the optimal policy in CVIU systems were developed, with focus on the single-input input case evaluated through a quadratic cost functional. These results are illustrated through a numerical example in economics.
Mestrado
Automação
Mestre em Engenharia Elétrica
30
Gessenharter, Dominik [Verfasser]. "Semantics-driven translation of UML-models into object-oriented programming languages : aligning the semantics of UML static structures and dynamic behavior in an approach for model-driven development / Dominik Gessenharter." Ulm : Universität Ulm, 2020. http://d-nb.info/1212115295/34.
Full text
31
Jackson, Zara. "Basal Metabolic Rate (BMR) estimation using Probabilistic Graphical Models." Thesis, Uppsala universitet, Statistiska institutionen, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-384629.
Full textAbstract:
Obesity is a growing problem globally. Currently 2.3 billion adults are overweight, and this number is rising. The most common method for weight loss is calorie counting, in which to lose weight a person should be in a calorie deficit. Basal Metabolic Rate accounts for the majority of calories a person burns in a day and it is therefore a major contributor to accurate calorie counting. This paper uses a Dynamic Bayesian Network to estimate Basal Metabolic Rate (BMR) for a sample of 219 individuals from all Body Mass Index (BMI) categories. The data was collected through the Lifesum app. A comparison of the estimated BMR values was made with the commonly used Harris Benedict equation, finding that food journaling is a sufficient method to estimate BMR. Next day weight prediction was also computed based on the estimated BMR. The results stated that the Harris Benedict equation produced more accurate predictions than the metabolic model proposed, therefore more work is necessary to find a model that accurately estimates BMR.
32
Zang, Peng. "Scaling solutions to Markov Decision Problems." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/42906.
Full textAbstract:
The Markov Decision Problem (MDP) is a widely applied mathematical model useful for describing a wide array of real world decision problems ranging from navigation to scheduling to robotics. Existing methods for solving MDPs scale poorly when applied to large domains where there are many components and factors to consider.
In this dissertation, I study the use of non-tabular representations and human input as scaling techniques. I will show that the joint approach has desirable optimality and convergence guarantees, and demonstrates several orders of magnitude speedup over conventional tabular methods. Empirical studies of speedup were performed using several domains including a clone of the classic video game, Super Mario Bros. In the course of this work, I will address several issues including: how approximate representations can be used without losing convergence and optimality properties, how human input can be solicited to maximize speedup and user engagement, and how that input should be used so as to insulate against possible errors.
33
Jottreau, Benoît. "Financial models and price formation : applications to sport betting." Thesis, Paris Est, 2009. http://www.theses.fr/2009PEST1031.
Full textAbstract:
Cette thèse est composée de quatre chapitres. Le premier chapitre traite de l'évaluation de produits financiers dans un modèle comportant un saut pour l'actif risque. Ce saut représente la faillite de l'entreprise correspondante. On étudie alors l'évaluation des prix d'options par indifférence d'utilité dans un cadre d'utilité exponentielle. Par des techniques de programmation dynamique on montre que le prix d'un Bond est solution d'une équation différentielle et le prix d'options dépendantes de l'actif est solution d'une équation aux dérives partielles d'Hamilton-Jacobi-Bellman. Le saut dans la dynamique de l'actif risque induit des différences avec le modèle de Merton que nous tentons de quantifier. Le second chapitre traite d'un marché comportant des sauts : les paris sur le football. Nous rappelons les différentes familles de modèles pour un match de football et introduisons un modèle complet permettant d'évaluer les prix des différents produits apparus sur ce marché ces dix dernières années. La complexité de ce modèle nous amène à étudier un modèle simplifié dont nous étudions les implications et calculons les prix obtenus que l'on compare à la réalité. On remarque que la calibration implicite obtenue génère de très bons résultats en produisant des prix très proches de la réalité. Le troisième chapitre développe le problème de fixation des prix par un teneur de marche monopolistique dans le marché des paris binaires. Ce travail est un prolongement direct au problème introduit par Levitt [Lev04]. Nous généralisons en effet son travail aux cas des paris européens et proposons une méthode pour estimer la méthode de cotation utilisée par le book-maker. Nous montrons que deux hypothèses inextricables peuvent expliquer cette fixation des prix. D'une part, l'incertitude du public sur la vraie valeur ainsi que le caractère extrêmement risque-averse du bookmaker. Le quatrième chapitre prolonge quant à lui cette approche au cas de produits financiers non binaires. Nous examinons différents modèles d'offre et de demande et en déduisons, par des techniques de programmation dynamique, des équations aux dérivées partielles dictant la formation des prix d'achat et de vente. Nous montrons finalement que l'écart entre prix d'achat et prix de vente ne dépend pas de la position du teneur de marche dans l'actif considère. Cependant le prix moyen dépend lui fortement de la quantité détenue par le teneur de marche. Une approche simplifiée est finalement proposée dans le cas multidimensionnelThis thesis is composed of four chapters. The first one deals with the pricing of financial products in a single jump model for the risky asset. This jump represents the bankrupcy of the quoted firm. We study the pricing of derivatives in the context of indifference of utility with an exponential utility. By means of dynamic programming we show that the bond price is solution of an ordinary differential equation and that stock price dependent options are solutions of an equation with partial derivatives of Hamilton-Jacobi-Bellman type generalizing the Black-Scholes one. We then try to quantify differences in the price obtained here and the one from Merton model without jump. The second chapter deals with a specific jump market : the soccer betting market. We recall the different model families for a soccer match and introduce some full model which allows to price the products recently born in this market in last ten years. Nevertheless the model complexity leads us to study a simplified model introduced by Dixon and Robinson from which we are able to derive closed formulas and simulate prices that we compare to market prices. We remark that implicit calibration gives pretty goof fit of market data. Third chapter developps the approach of Levitt [Lev04] on price formation in binary betting market held by a monopolistic market-maker operating in a one time step trading. We generalize Levitt results with european format of betting. We show that prices are distorded on the pressure of demand and offer, that phenomena introducing a market probability that allows to price products under this new measure. We identify some best model for demand and offer and market maker strategy and show that probability change is obvious in case of imperfect information about the value of the product. Fourth chapter generalizes this approach to the case of general payoffs and continuous time. The task is more complex and we just derive partial derivative equations from dynamic programming that enable us to give the bid-ask prices of the product traded by the market-maker. One result is that, in most models, bid-ask spread does not depend on the inventory held by the dealer whereas mid-quote price strongly reflects the unbalance of the dealer
34
Herrera, Cáceres Carlos Antonio. "Modeling and predictive control of a cash concentration and disbursements system." Doctoral thesis, Universitat Autònoma de Barcelona, 2016. http://hdl.handle.net/10803/399516.
Full textAbstract:
Esta tesis aborda el estudio de la Planificación financiera a corto plazo y la Gerencia de efectivo, a través del movimiento de dinero en las cuentas bancarias que participan en las decisiones financieras importantes de una empresa. La investigación se realiza en el marco de los modelos de planificación financiera corporativa, cuyo desarrollo se ha producido sobre todo en los últimos sesenta años. En particular, el trabajo se enfoca en los Sistemas de concentración de caja y desembolsos (CCDS), utilizados por las empresas para mejorar la planificación y el control de los activos corrientes y la Gerencia de efectivo. El objetivo de un CCDS es concentrar el efectivo disponible en una cuenta bancaria principal para hacer el mejor uso del dinero en grandes cantidades y, así, apoyar las operaciones de inversión y financiamiento. En consecuencia, la motivación principal de la tesis es lograr una representación exacta de un CCDS que permite su simulación numérica, análisis y evaluación, así como la posibilidad de nuevas investigaciones y el desarrollo de algoritmos para el soporte de decisiones financieras, basados en herramientas de la teoría de control. En este sentido, se presenta un modelo de simulación de un CCDS basado en ecuaciones en diferencias y técnicas de ingeniería de sistemas, incluyendo la existencia de retardos. Se supone la existencia de una cuenta principal operada de forma centralizada. La cual recibe transferencias de dinero desde las cuentas de ingreso de cada agencia de la empresa. También desde la cuenta principal, el dinero se transfiere hacia las cuentas de desembolso de las agencias para cubrir los sobregiros. El CCDS incluye también una cuenta de inversión para aprovechar los excedentes de efectivo y una línea de crédito para cubrir los déficits de caja. Adicionalmente, se deriva un modelo equivalente representado por ecuaciones algebraicas usando la transformada Z, posibilitando el uso de técnicas rigurosas de control en el campo financiero.
Bajo un enfoque descentralizado sobre el modelo del CCDS, se desarrolla un modelo de control predictivo (MPC) para una cuenta de ingresos, cuya aplicación se extiende a todas las agencias del sistema. Se utiliza Programación dinámica (DP) para el modelo de predicción que, a su vez, incluye un modelo de pronóstico estándar para la incertidumbre. EL MPC se simplifica procurando aliviar algunos de los problemas conocidos cuando DP se aplica bajo incertidumbre. También, se establece un sistema de bandas para la incertidumbre, limitando la entrada del modelo de DP, junto con un regulador de estabilización en forma de cascada que utiliza una ganancia de realimentación lineal. Esta combinación permite determinar un intervalo para la estabilidad del sistema indistintamente del tamaño del horizonte de predicción. La señal de referencia es una función de diente de sierra, que se adapta convenientemente a la política de inventario aplicada. La tesis muestra, en teoría y por medio de simulaciones, que el controlador propuesto cumple su objetivo. Por otra parte, se realiza una adaptación del MPC de la cuenta de ingresos, agregándole tiempo de retardo al modelo, con el propósito de utilizarlo para el control de las cuentas de desembolso. En consecuencia, se ofrecen dos propuestas de MPC para el problema de la cobertura de sobregiro. Por último, se presenta un caso de estudio utilizando datos hipotéticos para probar el modelo de simulación del CCDS. La ejecución del modelo ha permitido realizar un análisis exhaustivo de los resultados mostrando sus potencialidades y la versatilidad para adaptarse a diferentes escenarios realistas. Esta investigación abre un abanico de posibilidades para futuras investigaciones en las que se combinan las técnicas y teorías de la ingeniería de sistemas y de control, aplicados al ámbito financiero corporativo.This thesis addresses the study of cash management and short-term financial planning through the movement of money in bank accounts involved in the important financial decisions of a firm. The research is carried within the framework of models for corporate financial planning, whose development has mostly occurred in the last sixty years. Particularly, the work focuses on the Cash Concentration and Disbursements Systems (CCDS), which are used by firms for the purpose of improving the planning and control of current assets and cash management. The aim of a CCDS is to concentrate available cash in a main bank account in order to make best use of money in large amounts to support investment and financing operations. Consequently, the main motivation of the thesis is to achieve an accurate representation of a CCDS, allowing its numerical simulation, analysis and evaluation, as well as the subsequent possibility of exploring new researches and the development of algorithms for the financial decisions support, based on tools of control theory. In this regard, a simulation model of a CCDS seen as an inventory management system is presented, based on difference equations and systems engineering techniques including the existence of delays due to banking procedures. The model assumes the existence of a centrally operated main account. This account receives money transfers from the revenue accounts of each agency. Also from the main account, money is transferred to the agencies' disbursements accounts in order to cover overdrafts. There exist an investment account into which any cash surpluses of the main account are deposited and a credit line in order to avoid the cash deficits. The operating rules for the CCDS are defined, and income and financial costs involved are considered. The model represents the flow of money between the identified elements of the system and the flow of money requirements or transfer orders. An equivalent model represented by algebraic equations through the Z-transform is derived, which allows using rigorous control techniques in the field of finance. Based on a decentralized approach on the model of the CCDS, a Model Predictive Control (MPC) for a revenue account is developed, which is applied to all agencies. Dynamic Programming (DP) is used for the prediction model by including a standard forecasting model for uncertainty. Simplifications of the MPC are included seeking alleviate some of the known problems when DP is applied under uncertainty. Moreover, a band for the uncertainty is established to narrow the input of the DP model, together with a stabilizing regulator in cascade fashion using a linear feedback gain (closed-loop). This combination allows determining a range for the system stability regardless of the size of the prediction horizon. The reference signal used is a sawtooth function, which conveniently adapts to the inventory policy applied. Theoretically, and through simulation, it is shown that the proposed controller meets the control objective. The MPC of the revenue account is adapted by adding delay time in order to be used for disbursement accounts. Accordingly, two proposals of a model predictive control are provided on the overdraft coverage problem. Finally, a case study is presented using hypothetical data in order to test the simulation model of the CCDS. Running the model allows performing a comprehensive analysis of results showing its potentialities and the versatility to suit different realistic scenarios. This research opens up a range of possibilities for further research in which techniques and theories of systems engineering and control are combined, applied to corporate financial field.
35
Prum, Sophea. "On the use of a discriminant approach for handwritten word recognition based on bi-character models." Thesis, La Rochelle, 2013. http://www.theses.fr/2013LAROS418/document.
Full textAbstract:
Avec l’avènement des dispositifs nomades tels que les smartphones et les tablettes, la reconnaissance automatique de l’écriture manuscrite cursive à partir d’un signal en ligne est devenue durant les dernières décennies un besoin réel de la vie quotidienne à l’ère numérique. Dans le cadre de cette thèse, nous proposons de nouvelles stratégies pour un système de reconnaissance de mots manuscrits en-ligne. Ce système se base sur une méthode collaborative segmentation/reconnaissance et en utilisant des analyses à deux niveaux : caractère et bi-caractères. Plus précisément, notre système repose sur une segmentation de mots manuscrits en graphèmes afin de créer un treillis à L niveaux. Chaque noeud de ce treillis est considéré comme un caractère potentiel envoyé à un moteur de Reconnaissance de Caractères Isolés (RCI) basé sur un SVM. Pour chaque noeud, ce dernier renvoie une liste de caractères associés à une liste d’estimations de probabilités de reconnaissance. Du fait de la grande diversité des informations résultant de la segmentation en graphèmes, en particulier à cause de la présence de morceaux de caractères et de ligatures, l’injection de chacun des noeuds du treillis dans le RCI engendre de potentielles ambiguïtés au niveau du caractère. Nous proposons de lever ces ambiguïtés en utilisant des modèles de bi-caractères, basés sur une régression logistique dont l’objectif est de vérifier la cohérence des informations à un niveau de reconnaissance plus élevé. Finalement, les résultats renvoyés par le RCI et l’analyse des modèles de bi-caractères sont utilisés dans la phase de décodage pour parcourir le treillis dans le but de trouver le chemin optimal associé à chaque mot dans le lexique. Deux méthodes de décodage sont proposées (recherche heuristique et programmation dynamique), la plus efficace étant basée sur de la programmation dynamiqueWith the advent of mobile devices such as tablets and smartphones over the last decades, on-line handwriting recognition has become a very highly demanded service for daily life activities and professional applications. This thesis presents a new approach for on-line handwriting recognition. This approach is based on explicit segmentation/recognition integrated in a two level analysis system: character and bi-character. More specifically, our system segments a handwritten word in a sequence of graphemes to be then used to create a L-levels lattice of graphemes. Each node of the lattice is considered as a character to be submitted to a SVM based Isolated Character Recognizer (ICR). The ICR returns a list of potential character candidates, each of which is associated with an estimated recognition probability. However, each node of the lattice is a combination of various segmented graphemes. As a consequence, a node may contain some ambiguous information that cannot be handled by the ICR at character level analysis. We propose to solve this problem using "bi-character" models based on Logistic Regression, in order to verify the consistency of the information at a higher level of analysis. Finally, the recognition results provided by the ICR and the bi-character models are used in the word decoding stage, whose role is to find the optimal path in the lattice associated to each word in the lexicon. Two methods are presented for word decoding (heuristic search and dynamic programming), and dynamic programming is found to be the most effective
36
Poire, Xavier Corvera. "Model generation and sampling algorithms for dynamic stochastic programming." Thesis, University of Essex, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.294674.
Full text
37
BRANCO, ADRIANO FRANCISCO. "A WSN PROGRAMMING MODEL WITH A DYNAMIC RECONFIGURATION SUPPORT." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2011. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=18309@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIORAlgumas características básicas das redes de sensores sem fio (RSSF) dificultam as tarefas de criação e reconfiguração de aplicações. Nesse trabalho apresentamos um modelo de programação que pretende simplificar essas tarefas. O modelo se baseia no uso conjunto de funções parametrizáveis e de máquinas de estados finitos, e permite a implementação de diferentes tipos de aplicações para redes de sensores sem fio e a configuração remota dessas aplicações. Descrevemos alguns testes para avaliar o quanto esse modelo pode facilitar o desenvolvimento de novas aplicações, o quanto é fácil aplicar novas alterações sobre as aplicaçõesem execuçãos, e o impacto na quantidade de mensagens na rede por conta do uso da configuração remota.
Some basic characteristics of wireless sensor networks (WSN) make application creation and reconfiguration dificult tasks. A programming model is presented to simplify these tasks. This model is based on a set of parametrized components and on a Finite State Machine, and allows the remote configuration of different applications over the same set of installed components. We describe some tests to evaluate its impact on the development process, and the ease of applying modifications to a running application. We also measure the additional impact of remote configuration on network activity.
38
Zhao, Mengyao. "Genomic variation detection using dynamic programming methods." Thesis, Boston College, 2014. http://hdl.handle.net/2345/bc-ir:104357.
Full textAbstract:
Thesis advisor: Gabor T. MarthBackground: Due to the rapid development and application of next generation sequencing (NGS) techniques, large amounts of NGS data have become available for genome-related biological research, such as population genetics, evolutionary research, and genome wide association studies. A crucial step of these genome-related studies is the detection of genomic variation between different species and individuals. Current approaches for the detection of genomic variation can be classified into alignment-based variation detection and assembly-based variation detection. Due to the limitation of current NGS read length, alignment-based variation detection remains the mainstream approach. The Smith-Waterman algorithm, which produces the optimal pairwise alignment between two sequences, is frequently used as a key component of fast heuristic read mapping and variation detection tools for next-generation sequencing data. Though various fast Smith-Waterman implementations are developed, they are either designed as monolithic protein database searching tools, which do not return detailed alignment, or they are embedded into other tools. These issues make reusing these efficient Smith-Waterman implementations impractical. After the alignment step in the traditional variation detection pipeline, the afterward variation detection using pileup data and the Bayesian model is also facing great challenges especially from low-complexity genomic regions. Sequencing errors and misalignment problems still influence variation detection (especially INDEL detection) a lot. The accuracy of genomic variation detection still needs to be improved, especially when we work on low- complexity genomic regions and low-quality sequencing data. Results: To facilitate easy integration of the fast Single-Instruction-Multiple-Data Smith-Waterman algorithm into third-party software, we wrote a C/C++ library, which extends Farrar's Striped Smith-Waterman (SSW) to return alignment information in addition to the optimal Smith-Waterman score. In this library we developed a new method to generate the full optimal alignment results and a suboptimal score in linear space at little cost of efficiency. This improvement makes the fast Single-Instruction-Multiple-Data Smith-Waterman become really useful in genomic applications. SSW is available both as a C/C++ software library, as well as a stand-alone alignment tool at: https://github.com/mengyao/Complete- Striped-Smith-Waterman-Library. The SSW library has been used in the primary read mapping tool MOSAIK, the split-read mapping program SCISSORS, the MEI detector TAN- GRAM, and the read-overlap graph generation program RZMBLR. The speeds of the mentioned software are improved significantly by replacing their ordinary Smith-Waterman or banded Smith-Waterman module with the SSW Library. To improve the accuracy of genomic variation detection, especially in low-complexity genomic regions and on low-quality sequencing data, we developed PHV, a genomic variation detection tool based on the profile hidden Markov model. PHV also demonstrates a novel PHMM application in the genomic research field. The banded PHMM algorithms used in PHV make it a very fast whole-genome variation detection tool based on the HMM method. The comparison of PHV to GATK, Samtools and Freebayes for detecting variation from both simulated data and real data shows PHV has good potential for dealing with sequencing errors and misalignments. PHV also successfully detects a 49 bp long deletion that is totally misaligned by the mapping tool, and neglected by GATK and Samtools. Conclusion: The efforts made in this thesis are very meaningful for methodology development in studies of genomic variation detection. The two novel algorithms stated here will also inspire future work in NGS data analysis
Thesis (PhD) — Boston College, 2014
Submitted to: Boston College. Graduate School of Arts and Sciences
Discipline: Biology
39
Wang, Shi'an. "Stochastic Dynamic Model of Urban Traffic and Optimum Management of Its Flow and Congestion." Thesis, Université d'Ottawa / University of Ottawa, 2018. http://hdl.handle.net/10393/37254.
Full textAbstract:
There are a lot more roads being built periodically in most of the countries with the advancement of modern society. In order to promote the overall traffic flow quality within different cities, city traffic management has been playing a more and more essential role during the last few decades. In recent years, a significantly increasing attention has been paid to the management of traffic flow in major cities all over the world.
In this thesis, we develop a stochastic dynamic model for urban traffic along with physical constraints characteristic of intersections equipped with traffic light. We assume that the incoming traffic to each stream in an intersection is amenable to the Poisson random process with variable intensity (mean). We introduce expressions for traffic throughput, congestion as well as operator's waiting time for the typical intersection in a city and hereafter define an appropriate objective functional. Afterwards, we formulate an optimization problem and propose the sequential (or recursive) algorithm based on the principle of optimality (dynamic programming) due to Bellman. The solution if implemented is expected to improve throughput, reduce congestion, and promote driver's satisfaction. Because the dynamic programming method is computationally quite intensive, we consider the scenario that one unit traffic stream stands for a specific number of vehicles which actually depends on the volume of traffic flow through the intersection.
The system is simulated with inputs described by several distinct nonhomogeneous Poisson processes. For example, we apply the typical traffic arrival rate in Canada with morning peak hour at around 7:30 AM and afternoon peak hour at around 4:30 PM whilst it is also applied with morning rush hour at about 8:00 AM and afternoon rush hour at about 6:00 PM like in China. In the meanwhile, we also present a group of numerical results for the traffic arrival rates that have shorter morning peak-hour period but longer afternoon rush hour period. This may occasionally happen when there are some social activities or big events in the afternoon. In addition, another series of experiments are carried out to illustrate the feasibility of the proposed dynamic model based on the traffic arrival rates with only one peak-hour throughout the whole day. The system is simulated with a series of experiments and the optimization problem is solved by dynamic programming based on the proposed algorithm which gives us the optimal feedback control law. More specifically, the results show that both the optimal traffic light timing allocated for each stream and the congestion broadcast level (CBL) of each road segment during each time segment are found. Accordingly, the corresponding optimal cost can be found for any given initial condition. It is reasonably believed that this stochastic dynamic model would be potentially applicable for real time adaptive traffic control system.
40
Hammoudan, Zakaria. "Production and delivery integrated scheduling problems in multi-transporter multi-custumer supply chain with costs considerations." Thesis, Belfort-Montbéliard, 2015. http://www.theses.fr/2015BELF0267/document.
Full textAbstract:
La coordination des activités dans une chaîne logistique a suscité récemment beaucoup d'attention dans larecherche de gestion. Dans une chaîne logistique typique, des produits finis sont produits et transportés pour êtrestockage temporairement ou arriver directement chez clients. Pour réaliser la représentation opérationnelleoptimale, la coordination et l'intégration de la production, de la livraison, et du stockage devient très importante.L'étude récente a considéré le coût de stockage de client avec le coût fixe de transport ou la taille fixe des lots, cequi est irréaliste.Dans cette thèse, nous étudions la coordination de traitement des produits en lots et l'ordonnancement des lots, quiinclut la coordination du traitement en lots des produits dans les groupes après l'étape de production,l'ordonnancement des lots après les productions exigent la livraison du fournisseur ainsi que le stockage desproduits aux clients. Ce travail focalise sur les cas du simple-fournisseur/plusieurs-clients et le cas de simplefournisseur/plusieurs-transporteurs. Pour le premier scénario avec plusieurs-clients, deux modèles illustrent letransfert des lots aux clients. Dans le premier modèle, nous avons considéré un simple-fournisseur/plusieurs-clientsavec un transporteur disponible pour servir les clients sans considération du problème de tournée de véhicule. Puis,dans le deuxième modèle, nous avons considéré un simple-fournisseur/plusieurs-clients avec plusieurs transportersdisponibles pour servir les clients. Différentes hypothèses sont proposées et comparées dans le dernier chapitre.Pour ce qui concerne le deuxième scénario, nous avons étudié le cas du simple-fournisseur avec plusieurstransporteurs disponibles pour servir un seul client. Dans ce scénario, des modèles avec les véhicules homogèneset hétérogènes sont étudiés. Tout le coût du système est calculé en additionnant de tout le coût de la livraison et destockage pour les différents clients et transporteurs qui se sont dans le système à étudier. Le nombre des produitsdans les lots peut être inégal et les lots sont limités seulement par la capacité du transporteur utilisé. Le coût destockage chez les clients dépend de chaque client, la distance entre le fournisseur et leurs clients dépend del'emplacement de client, qui est le cas du coût de livraison également qui dépend de l'emplacement du client. Dansle cas des multi transporteurs, le coût de livraison dépend du transporteur utilisé.Dans chaque modèle, nous présentons ce qui suit : procédures de solution pour résoudre chaque modèle, plusieursexemples numériques pour soutenir des résultats mathématiques et pour clarifier le problème, et comparaisons desperformances parmi différents résultats. La future extension de cette recherche peut considérer des contraintes detemps et de coût de chargement dans l'étape de production, la considération du tourné de véhicule avec un cout destockage chez les clientsThe coordination of logistics activities in a supply chain has recently received a lot of attention in operationsmanagement research. In a typical supply chain, finished products are produced and either shipped to be temporarystorage or arrived directly on time to the customers. To achieve optimal operational performance, the coordinationand integration of production, delivery, and storage is an important consideration. The recent study consideredcustomer storage cost with fixed transportation cost or fixed batch size, which is unrealistic. In this thesis, we studythe coordinate of batching and scheduling activities, which includes the coordination of batching of products inbatches after the production stage, the coordination of scheduling, customer(s) orders which require the deliveryfrom the supplier, and the storage of products at the customer(s). This study focus on single-supplier/multi-customerscenario and single-supplier/multi-transporter scenario. For the first scenario with multi-customer, two modelsillustrate the transferring of batches to the customer. Where in the first model, we considered a singlesupplier/ multicustomerwith one capacitated transporter available to serve the customers without the vehicle routingconsideration. Then, in the second model, we considered a single-supplier/multi-customer with multi-transportavailable to serve the customers. In this case different assumption is proposed and compared in the last chapter.Concerning the second scenario, we studied the case of single-supplier with multi-transporter available to serve asingle customer. In this scenario, models with homogeneous and heterogeneous vehicles are studied. The totalsystem cost is calculated by summing the total delivery and storage cost for different customers and transporters inthe system. The number of products by batch is unequal and they are limited only by the capacity of the transporterused. The storage cost of the customers depends on the customer destination, the distance between the supplierand their customers depends on the customer location, which is the case of the delivery cost also which depends onthe customer¿s location. In the case of the multi-transporters, the delivery cost depends on the transporter used.In each model, we present the following: solution procedures to solve each model, many numerical examples tosupport mathematical findings and to clarify the problem under study, and performance comparisons amongdifferent findings. The future extension of this research may involve considering setup time and cost constraints inthe production stage, the vehicle routing consideration with inventory in the multi-customer case
41
O'Connell, Jonathan F. "A dynamic programming model to solve optimisation problems using GPUs." Thesis, Cardiff University, 2017. http://orca.cf.ac.uk/97930/.
Full textAbstract:
This thesis presents a parallel, dynamic programming based model which is deployed on the GPU of a system to accelerate the solving of optimisation problems. This is achieved by simultaneously running GPU based computations, and memory transactions, allowing computation to never pause, and overcoming the memory constraints of solving large problem instances. Due to this some optimisation problems, which are currently not solved in an exact manner for real world sized instances due to their complexity, are moved into the solvable realm. The model is implemented to solve, a range of different test problems, where artificially constructed test data is used to ensure good performance even in the worst cases. Through this extensive testing, we can be confident the model will perform well when used to solve real world test cases. Testing of the model was carried out using a range of different implementation parameters in relation to deployment on the GPU, in order to identify both optimal implementation parameters, and how the model will operate when running on different systems. All problems, when implemented in parallel using the model, show run-time improvements compared to the sequential implementations, in some instances up to hundreds of times faster, but more importantly also show high efficiency metrics for the utilisation of GPU resources. Throughout testing emphasis has been placed on GPU based metrics to ensure the wider generic applicability of the model. Finally, the parallel model allows for new problems to be defined through the use of a simple file format, enabling wider usage of the model.
42
Gargesa, Padmashri. "Reward-driven Training of Random Boolean Network Reservoirs for Model-Free Environments." PDXScholar, 2013. https://pdxscholar.library.pdx.edu/open_access_etds/669.
Full textAbstract:
Reservoir Computing (RC) is an emerging machine learning paradigm where a fixed kernel, built from a randomly connected "reservoir" with sufficiently rich dynamics, is capable of expanding the problem space in a non-linear fashion to a higher dimensional feature space. These features can then be interpreted by a linear readout layer that is trained by a gradient descent method. In comparison to traditional neural networks, only the output layer needs to be trained, which leads to a significant computational advantage. In addition, the short term memory of the reservoir dynamics has the ability to transform a complex temporal input state space to a simple non-temporal representation. Adaptive real-time systems are multi-stage decision problems that can be used to train an agent to achieve a preset goal by performing an optimal action at each timestep. In such problems, the agent learns through continuous interactions with its environment. Conventional techniques to solving such problems become computationally expensive or may not converge if the state-space being considered is large, partially observable, or if short term memory is required in optimal decision making. The objective of this thesis is to use reservoir computers to solve such goal-driven tasks, where no error signal can be readily calculated to apply gradient descent methodologies. To address this challenge, we propose a novel reinforcement learning approach in combination with reservoir computers built from simple Boolean components. Such reservoirs are of interest because they have the potential to be fabricated by self-assembly techniques. We evaluate the performance of our approach in both Markovian and non-Markovian environments. We compare the performance of an agent trained through traditional Q-Learning. We find that the reservoir-based agent performs successfully in these problem contexts and even performs marginally better than Q-Learning agents in certain cases. Our proposed approach allows to retain the advantage of traditional parameterized dynamic systems in successfully modeling embedded state-space representations while eliminating the complexity involved in training traditional neural networks. To the best of our knowledge, our method of training a reservoir readout layer through an on-policy boot-strapping approach is unique in the field of random Boolean network reservoirs.
43
Wongthatsanekorn, Wuthichai. "Strategic Network Growth with Recruitment Model." Diss., Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/14636.
Full textAbstract:
In order to achieve stable and sustainable systems for recycling post-consumer goods, it is frequently necessary to concentrate the flows from many collection points to meet the volume requirements for the recycler. This motivates the importance of growing the collection network over time to both meet volume targets and keep costs to a minimum. This research addresses a complex and interconnected set of strategic and tactical decisions that guide the growth of reverse supply chain networks over time. This dissertation has two major components: a tactical recruitment model and a strategic investment model. These capture the two major decision levels for the system, the former for the regional collector who is responsible for recruiting material sources to the network, the latter for the processor who needs to allocate his scarce resources over time and to regions to enable the recruitment to be effective. The recruitment model is posed as a stochastic dynamic programming problem. An exact method and two heuristics are developed to solve this problem. A numerical study of the solution approaches is also performed. The second component involves a key set of decisions on how to allocate resources effectively to grow the network to meet long term collection targets and collection cost constraints. The recruitment problem appears as a sub-problem for the strategic model and this leads to a multi-time scale Markov decision problem. A heuristic approach which decomposes the strategic problem is proposed to solve realistically sized problems. The numerical valuations of the heuristic approach for small and realistically sized problems are then investigated.
44
Olofsson, Nils. "Kidney Dynamic Model Enrichment." Thesis, Uppsala universitet, Avdelningen för visuell information och interaktion, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-242315.
Full textAbstract:
This thesis explores and explains a method using discrete curvature as a feature to find regions of vertices that can be classified as being likely to indicate the presence of an underlying tumor on a kidney surface mesh. Vertices are tagged based on curvature type and mathematical morphology is used to form regions on the mesh. The size and location of the tumor is approximated by fitting a sphere to this region. The method is intended to be employed in noninvasive radiotherapy with a dynamic soft tissue model. It could also provide an alternative to volumetric methods used to segment tumors. A validation is made using the images from which the kidney mesh was constructed, the tumor is visible as a comparison to the method result. The dynamic kidney model is validated using the Hausdorff distance and it is explained how this can be computed in an effective way using bounding volume hierarchies. Both the tumor finding method and the dynamic model show promising results since they lie within the limit used by practitioners during therapy.
45
SANTOS, Watson Robert Macedo. "Metodos para Solução da Equação HJB-Riccati via Famíla de Estimadores Parametricos RLS Simplificados e Dependentes de Modelo." Universidade Federal do Maranhão, 2014. http://tedebc.ufma.br:8080/jspui/handle/tede/1892.
Full textAbstract:
Submitted by Maria Aparecida (cidazen@gmail.com) on 2017-09-04T13:42:58Z
No. of bitstreams: 1
Watson Robert.pdf: 2699368 bytes, checksum: cf204eec3df50b251f4adbbbd380ffd0 (MD5)Made available in DSpace on 2017-09-04T13:42:58Z (GMT). No. of bitstreams: 1 Watson Robert.pdf: 2699368 bytes, checksum: cf204eec3df50b251f4adbbbd380ffd0 (MD5) Previous issue date: 2014-08-21
Due to the demand for high-performance equipments and the rising cost of energy, the industrial sector is developing equipments to attend minimization of the theirs operational costs. The implementation of these requirements generate a demand for projects and implementations of high-performance control systems. The optimal control theory is an alternative to solve this problem, because in its design considers the normative specifications of the system design, as well as those that are related to the operational costs. Motivated by these perspectives, it is presented the study of methods and the development of algorithms to the approximated solution of the Equation Hamilton-Jacobi-Bellman, in the form of discrete Riccati equation, model free and dependent of the dynamic system. The proposed solutions are developed in the context of adaptive dynamic programming that are based on the methods for online design of optimal control systems, Discrete Linear Quadratic Regulator type. The proposed approach is evaluated in multivariable models of the dynamic systems to evaluate the perspectives of the optimal control law for online implementations.
Devido a demanda por equipamentos de alto desempenho e o custo crescente da energia, o setor industrial desenvolve equipamentos que atendem a minimização dos seus custos operacionais. A implantação destas exigências geram uma demanda por projetos e implementações de sistemas de controle de alto desempenho. A teoria de controle ótimo é uma alternativa para solucionar este problema, porque considera no seu projeto as especificações normativas de projeto do sistema, como também as relativas aos seus custos operacionais. Motivado por estas perspectivas, apresenta-se o estudo de métodos e o desenvolvimento de algoritmos para solução aproximada da Equação Hamilton-Jacobi-Bellman, do tipo Equação Discreta de Riccati, livre e dependente de modelo do sistema dinâmico. As soluções propostas são desenvolvidas no contexto de programação dinâmica adaptativa (ADP) que baseiam-se nos métodos para o projeto on-line de Controladores Ótimos, do tipo Regulador Linear Quadrático Discreto. A abordagem proposta é avaliada em modelos de sistemas dinâmicos multivariáveis, tendo em vista a implementação on-line de leis de controle ótimo.
46
Frey, Rüdiger, Abdelali Gabih, and Ralf Wunderlich. "Portfolio Optimization under Partial Information with Expert Opinions." World Scientific Publishing, 2012. http://epub.wu.ac.at/3844/1/Frey.pdf.
Full textAbstract:
This paper investigates optimal portfolio strategies in a market with partial information
on the drift. The drift is modelled as a function of a continuous-time Markov chain
with finitely many states which is not directly observable. Information on the drift is
obtained from the observation of stock prices. Moreover, expert opinions in the form
of signals at random discrete time points are included in the analysis. We derive the
filtering equation for the return process and incorporate the filter into the state variables
of the optimization problem. This problem is studied with dynamic programming
methods. In particular, we propose a policy improvement method to obtain computable
approximations of the optimal strategy. Numerical results are presented at the end. (author's abstract)
47
Yeung, Raymond Y. T. "Towards a family model of the labour market behaviour of immigrants, estimates of a discrete choice dynamic programming model." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0005/NQ42996.pdf.
Full text
48
Hellström, Erik. "Explicit use of road topography for model predictive cruise control in heavy trucks." Thesis, Linköping University, Department of Electrical Engineering, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-2843.
Full textAbstract:
New and exciting possibilities in vehicle control are revealed by the consideration of topography through the combination GPS and three dimensional road maps. This thesis explores how information about future road slopes can be utilized in a heavy truck with the aim at reducing the fuel consumption over a route without increasing the total travel time.
A model predictive control (MPC) scheme is used to control the longitudinal behavior of the vehicle, which entails determining accelerator and brake levels and also which gear to engage. The optimization is accomplished through discrete dynamic programming. A cost function is used to define the optimization criterion. Through the function parameters the user is enabled to decide how fuel use, negative deviations from the reference velocity, velocity changes, gear shifts and brake use are weighed.
Computer simulations with a load of 40 metric tons shows that the fuel consumption can be reduced with 2.5% with a negligible change in travel time, going from Link¨oping to J¨onk¨oping and back. The road slopes are calculated by differentiation of authentic altitude measurements along this route. The complexity of the algorithm when achieving these results allows the simulations to run two to four times faster than real time on a standard PC, depending on the desired update frequency of the control signals.
49
Arad, Cosmin Ionel. "Programming Model and Protocols for Reconfigurable Distributed Systems." Doctoral thesis, KTH, Programvaruteknik och Datorsystem, SCS, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-122311.
Full textAbstract:
Distributed systems are everywhere. From large datacenters to mobile devices, an ever richer assortment of applications and services relies on distributed systems, infrastructure, and protocols. Despite their ubiquity, testing and debugging distributed systems remains notoriously hard. Moreover, aside from inherent design challenges posed by partial failure, concurrency, or asynchrony, there remain significant challenges in the implementation of distributed systems. These programming challenges stem from the increasing complexity of the concurrent activities and reactive behaviors in a distributed system on the one hand, and the need to effectively leverage the parallelism offered by modern multi-core hardware, on the other hand. This thesis contributes Kompics, a programming model designed to alleviate some of these challenges. Kompics is a component model and programming framework for building distributed systems by composing message-passing concurrent components. Systems built with Kompics leverage multi-core machines out of the box, and they can be dynamically reconfigured to support hot software upgrades. A simulation framework enables deterministic execution replay for debugging, testing, and reproducible behavior evaluation for largescale Kompics distributed systems. The same system code is used for both simulation and production deployment, greatly simplifying the system development, testing, and debugging cycle. We highlight the architectural patterns and abstractions facilitated by Kompics through a case study of a non-trivial distributed key-value storage system. CATS is a scalable, fault-tolerant, elastic, and self-managing key-value store which trades off service availability for guarantees of atomic data consistency and tolerance to network partitions. We present the composition architecture for the numerous protocols employed by the CATS system, as well as our methodology for testing the correctness of key CATS algorithms using the Kompics simulation framework. Results from a comprehensive performance evaluation attest that CATS achieves its claimed properties and delivers a level of performance competitive with similar systems which provide only weaker consistency guarantees. More importantly, this testifies that Kompics admits efficient system implementations. Its use as a teaching framework as well as its use for rapid prototyping, development, and evaluation of a myriad of scalable distributed systems, both within and outside our research group, confirm the practicality of Kompics.QC 20130520
50
Arad, Cosmin. "Programming Model and Protocols for Reconfigurable Distributed Systems." Doctoral thesis, SICS, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:ri:diva-24202.
Full textAbstract:
Distributed systems are everywhere. From large datacenters to mobile devices, an ever richer assortment of applications and services relies on distributed systems, infrastructure, and protocols. Despite their ubiquity, testing and debugging distributed systems remains notoriously hard. Moreover, aside from inherent design challenges posed by partial failure, concurrency, or asynchrony, there remain significant challenges in the implementation of distributed systems. These programming challenges stem from the increasing complexity of the concurrent activities and reactive behaviors in a distributed system on the one hand, and the need to effectively leverage the parallelism offered by modern multi-core hardware, on the other hand. This thesis contributes Kompics, a programming model designed to alleviate some of these challenges. Kompics is a component model and programming framework for building distributed systems by composing message-passing concurrent components. Systems built with Kompics leverage multi-core machines out of the box, and they can be dynamically reconfigured to support hot software upgrades. A simulation framework enables deterministic execution replay for debugging, testing, and reproducible behavior evaluation for large-scale Kompics distributed systems. The same system code is used for both simulation and production deployment, greatly simplifying the system development, testing, and debugging cycle. We highlight the architectural patterns and abstractions facilitated by Kompics through a case study of a non-trivial distributed key-value storage system. CATS is a scalable, fault-tolerant, elastic, and self-managing key-value store which trades off service availability for guarantees of atomic data consistency and tolerance to network partitions. We present the composition architecture for the numerous protocols employed by the CATS system, as well as our methodology for testing the correctness of key CATS algorithms using the Kompics simulation framework. Results from a comprehensive performance evaluation attest that CATS achieves its claimed properties and delivers a level of performance competitive with similar systems which provide only weaker consistency guarantees. More importantly, this testifies that Kompics admits efficient system implementations. Its use as a teaching framework as well as its use for rapid prototyping, development, and evaluation of a myriad of scalable distributed systems, both within and outside our research group, confirm the practicality of Kompics.Kompics
CATS
REST