No description available.

Production compilers implement optimizing transformation rules for built-in types. What justifies applying these optimizing rules is the axioms that hold for built-in types and the built-in operations supported by these types. Similar axioms also hold for user-defined types and the operations defined on them, and therefore justify a set of optimization rules that may apply to user-defined types. Production compilers, however, do not attempt to construct and apply these optimization rules to user-defined types. Built-in types together the axioms that apply to them are instances of more general algebraic structures. So are user-defined types and their associated axioms. We use the technique of generic programming, a programming paradigm to design efficient, reusable software libraries, to identify the commonality of classes of types, whether built-in or user-defined, convey the semantics of the classes of types to compilers, design scalable and effective program analysis for them, and eventually apply optimizing rules to the operations on them. In generic programming, algorithms and data structures are defined in terms of such algebraic structures. The same definitions are reused for many types, both built-in and user-defined. This dissertation applies generic programming to compiler analyses and transformations. Analyses and transformations are specified for general algebraic structures, and they apply to all types, both built-in and primitive types.

The development of infectious disease models remains important to provide scientists with tools to better understand disease dynamics and develop more effective control strategies. In this work we focus on the estimation of seasonally varying transmission parameters in infectious disease models from real measles case data. We formulate both discrete-time and continuous-time models and discussed the benefits and shortcomings of both types of models. Additionally, this work demonstrates the flexibility inherent in large-scale nonlinear programming techniques and the ability of these techniques to efficiently estimate transmission parameters even in very large-scale problems. This computational efficiency and flexibility opens the door for investigating many alternative model formulations and encourages use of these techniques for estimation of larger, more complex models like those with age-dependent dynamics, more complex compartment models, and spatially distributed data. How- ever, the size of these problems can become excessively large even for these powerful estimation techniques, and parallel estimation strategies must be explored. Two parallel decomposition approaches are presented that exploited scenario based de- composition and decomposition in time. These approaches show promise for certain types of estimation problems.

The Insight Segmentation and Registration Toolkit (ITK) is a long-established image processing library used for image analysis, visualisation, and image-guided surgery applications. ITK is a collection of C++ classes that can potentially pose usability problems for users without appropriate C++ programming experience. In order to remove the programming complexities and facilitate rapid prototyping, an implementation of ITK within a higher-level visual programming environment is presented: SimITK. ITK functionalities are automatically wrapped into "blocks" within the visual programming environment of MATLAB, Simulink, where these blocks can be connected to form workflows: visual schematics that closely represent the structure of a C++ program. The heavily C++ templated nature of ITK does not facilitate direct interaction between Simulink and ITK; an intermediary is required to convert respective datatypes and allow intercommunication. As such, a SimITK "Virtual Block" has been developed that serves as a wrapper around the ITK class responsible for resolving the datatypes used by ITK to native types used by Simulink. Part of this challenge surrounds the automated capturing and storage of the pertinent class information (name, inputs/outputs, acceptable datatypes, and allowed dimensionalities) that needs to be reflected within the final block representation. The WrapITK package, included with ITK, serves to generate initial class representations as complex eXtended Markup Language (XML) files that are consolidated and refined to organise the information into an easily accessible structure when extracting during wrapping. Once refined, the data are transferred into custom-written SimITK-templates - one template for each required filetype - through a series of custom-keyword substitutions that replace special keywords with appropriately retrieved XML information and/or programming code. The primary result from the SimITK wrapping procedure is the generation of multiple Simulink Block libraries. From these libraries, blocks are selected and interconnected to demonstrate case study examples: a 3D segmentation workflow using cranial-CT data and a 3D MRI-to-CT registration workflow. Suggestions for future development are included as well as several appendices containing a list of classes, code comparisons between ITK C++ and SimITK workflow, installation documentation (both user and developer), as well as example file templates used to integrate ITK within Simulink. / Thesis (Master, Computing) -- Queen's University, 2011-09-13 16:48:53.906

Constraint satisfaction problems (CSPs) provide a unified framework for studying a wide variety of computational problems naturally arising in combinatorics, artificial intelligence and database theory. To any finite domain D and any constraint language Γ (a finite set of relations over D), we associate the constraint satisfaction problem CSP(Γ): an instance of CSP(Γ) consists of a list of variables x1, x2,..., x n and a list of constraints of the form "(x 7, x2,..., x5) ∈ R" for some relation R in Γ. The goal is to determine whether the variables can be assigned values in D such that all constraints are simultaneously satisfied. The computational complexity of CSP(Γ) is entirely determined by the structure of the constraint language Γ and, thus, one wishes to identify classes of Γ such that CSP(Γ) belongs to a particular complexity class. / In recent years, logical and algebraic perspectives have been particularly successful in classifying CSPs. A major weapon in the arsenal of the logical perspective is the database-theory-inspired logic programming language called Datalog. A Datalog program can be used to solve a restricted class of CSPs by either accepting or rejecting a (suitably encoded) set of input constraints. Inspired by Dalmau's work on linear Datalog and Reingold's breakthrough that undirected graph connectivity is in logarithmic space, we use a new restriction of Datalog called symmetric Datalog to identify a class of CSPs solvable in logarithmic space. We establish that expressibility in symmetric Datalog is equivalent to expressibility in a specific restriction of second order logic called Symmetric Restricted Krom Monotone SNP that has already received attention for its close relationship with logarithmic space. / We also give a combinatorial description of a large class of CSPs lying in L by showing that they are definable in symmetric Datalog. The main result of this thesis is that directed st-connectivity and a closely related CSP cannot be defined in symmetric Datalog. Because undirected st-connectivity can be defined in symmetric Datalog, this result also sheds new light on the computational differences between the undirected and directed st-connectivity problems.

The topic of the dissertation is revision programming. It is a knowledge representation formalismfor describing constraints on databases, knowledge bases, and belief sets, and providing acomputational mechanism to enforce them. Constraints are represented by sets of revision rules.Revision rules could be quite complex and are usually in a form of conditions (for instance, ifthese elements are present and those elements are absent, then this element must be absent). Inaddition to being a logical constraint, a revision rule specify a preferred way to satisfy the constraint.Justified revisions semantics assigns to any database a set (possibly empty) of revisions.Each revision satisfies the constraints, and all deletions and additions of elements in a transitionfrom initial database to the revision are derived from revision rules.Revision programming and logic programming are closely related. We established an elegantembedding of revision programs into logic programs, which does not increase the size of a program.Initial database is used in transformation of a revision program into the corresponding logicprogram, but it is not represented in the logic program.The connection naturally led to extensions of revision programming formalism which correspondto existing extensions of logic programming. More specific, a disjunctive and a nestedversions of revision programming were introduced.Also, we studied annotated revision programs, which allow annotations like confidence factors,multiple experts, etc. Annotations were assumed to be elements of a complete infinitely distributivelattice. We proposed a justified revisions semantics for annotated revision programs which agreedwith intuitions.Next, we introduced definitions of well-founded semantics for revision programming. It assignsto a revision problem a single "intended" model which is computable in polynomial time.Finally, we extended syntax of revision problems by allowing variables and implemented translatorsof revision programs into logic programs and a grounder for revision programs. The implementationallows us to compute justified revisions using existing implementations of the stablemodel semantics for logic programs.

Solution of any search problem lies in its search space. A search is a systematic examination of candidate solutions of a search problem. In this thesis, we present a search heuristic that we can cr-smodels. cr-smodels prunes the search space to quickly reach to the solution of a problem. The idea is to pick an atom for branching , that lowers the growth rate of the linear recurrence and thuse, minimizes the remaining search space. Our goal in developing cr-smodels is to develop a search heuristic that is efficient on a wide range of problems. Then, we test cr-smodels over a wide range of randomly generated benchmarks. we observed that often randomly generated graphs with no Hamiltonian cycle were trivial to solve. Since, Hamiltonian cycle is an important benchmark problem, my other goal is to develop techniques that generate hard instances of graphs with no Hamiltonian cycle.

This thesis studies an inventory-location problem faced by a large manufacturer and supplier of small to medium sized aircraft and their spare parts. The sale of after market spare parts is a major source of revenue for the company, but it is a complex industry with many unique challenges. The original problem is a multi-echelon network design problem, which is decomposed into a facility location problem with consolidated shipping challenges, and a spare parts inventory problem. The facility location problem is solved a number of times under different scenarios to give the company's leadership team access to a wide range of feasible solutions. The model itself is an important contribution to industry, allowing the company to solve a spare parts network problem that will guide strategic decision-making for years. The chapter serves as case-study on how to accurately model a large and complicated service parts supply chain through the use of mathematical programming, part aggregation and scenarios. The company used the scenario results to redesign its spare parts distribution network, opening new hubs and consolidating existing service centres. The costs savings associated with this project are estimated to be $4.4 Million USD annually. The proposed solution does increase the burden of customer freight charges on the company's customers compared to the current network, but the operational savings are expected to more than outweigh the increase in customer shipments costs. The project team thus recommended that the company consider subsidizing customer freight costs to offset the expected cost increase the customers face, resulting in lower costs for both the company and their customers. This solution could set a new standard for aircraft spare parts suppliers to follow. Considered next is an integrated inventory-location problem with service requirements based on the first problem. Customer demand is Poisson distributed and the service levels are time-based, leading to highly non-linear, stochastic service constraints and a nonlinear, mixed-integer optimization problem. Unlike previous works in the literature that propose approximations for the nonlinear constraints, this thesis presents an exact solution methodology using logic-based Benders decomposition. The problem is decomposed to separate the location decisions in the master problem from the inventory decisions in the subproblem. A new family of valid cuts is proposed and the algorithm is shown to converge to optimality. This is the first attempt to solve this type of problem exactly. Then, this thesis presents a new restrict-and-decompose scheme to further decompose the Benders master problem by part. The approach is tested on industry instances as well as random instances. The second algorithm is able to solve industry instances with up to 60 parts within two hours of computation time, while the maximum number of parts attempted in the literature is currently five. Finally, this thesis studies a second integrated inventory-location problem under different assumptions. While the previous model uses the backorder assumption for unfilled demand and a strict time window, the third model uses the lost-sales assumption and a soft time window for satisfying time sensitive customer demand. The restrict-and-decompose scheme is applied with little modification, the main difference being the calculation of the Benders cut coefficients. The algorithm is again guaranteed to converge to optimality. The results are compared against previous work under the same assumptions. The results deliver better solutions and certificates of optimality to a large set of test problems.

Thesis (M.Ed.)--North-West University, Potchefstroom Campus, 2010.

Thesis (M.Ed.)--North-West University, Potchefstroom Campus, 2010.