München, Techn. Univ., Diss., 2009.

La technologie multi-coeur et les architectures massivement parallèles sont de plus en plus accessibles à tous, à travers des technologies comme le Xeon Phi ou les cartes GPU. Cette stratégie d’architecture a été communément adoptée par les constructeurs pour faire face à la loi de Moore. Or, ces nouvelles architectures impliquent d’autres manières de concevoir et d’implémenter les algorithmes, pour exploiter complètement leur potentiel, en particulier dans le cas des solveurs de contraintes traitant de problèmes d’optimisation combinatoire. De plus, le temps de développement nécessaire pour coder des solveurs en parallèle est souvent sous-estimée, et concevoir des algorithmes efficaces pour résoudre certains problèmes consomme trop de temps. Dans cette thèse nous présentons le langage orienté parallèle POSL, permettant de construire des solveurs de contraintes basés sur des méta-heuristiques qui résolvent des Problèmes de Satisfaction de Contraintes. Le but de ce travail est d’obtenir un système pour facilement construire des solveurs et réduire l’effort de leur développement en proposant un mécanisme de réutilisation de code entre les différents solveurs. Il fournit aussi un mécanisme pour coder des stratégies de communication indépendantes des solveurs. Dans cette thèse, nous présentons aussi une analyse détaillée des résultats obtenus en résolvant plusieurs instances des CSPs. L’idée n’est pas d’améliorer l’état de l’art en terme d’efficacité sur ces instances de CSPs, mais de démontrer qu’il est possible de rapidement écrire des prototypes avec POSL afin d’expérimenter facilement différentes stratégies de communication. / The multi-core technology and massive parallel architectures are nowadays more accessible for a broad public through hardware like the Xeon Phi or GPU cards. This architecture strategy has been commonly adopted by processor manufacturers to stick with Moore’s law. However, this new architecture implies new ways of designing and implementing algorithms to exploit their full potential. This is in particular true for constraint-based solvers dealing with combinatorial optimization problems. Furthermore, the developing time needed to code parallel solvers is often underestimated. In fact, conceiving efficient algorithms to solve certain problems takes a considerable amount of time. In this thesis we present POSL, a Parallel-Oriented Solver Language for building solvers based on meta-heuristic in order to solve Constraint Satisfaction Problems (CSP) in parallel. The main goal of this thesis is to obtain a system with which solvers can be easily built, reducing therefore their development effort by proposing a mechanism for code reusing between solvers. It also provides a mechanism to implement solver-independent communication strategies. We also present a detailed analysis of the results obtained when solving some CSPs. The goal is not to outperform the state–of–the–art solvers in terms of efficiency, but to show that it is possible to rapidly prototype with POSL in order to experiment different communication strategies.

Une large gamme de problèmes pratiques nécessite une diversité de représentation et de modélisation des données et de développer des modèles dans lesquels les différentes données peuvent être représentées. Dans cette thèse, nous nous intéressons à l'hybridation de deux modèles : le modèle des Systèmes Experts (SE) et le modèle des Problèmes de Satisfaction de Contraintes (CSP). L'objectif de notre travail est de proposer un système distribué et sécurisé pour intégrer des contraintes dans un moteur d'inférence. Pour ce faire, nous avons d'une part développé un outil de communication qui facilite la collaboration entre SE et CSP. D'autre part, nous avons conçu un algorithme qui permet la communication entre plusieurs agents situés dans un environnement distribué. Enfin, un de nos buts, et non des moindres, est d'assurer la protection des données privées de chaque entité. La thèse est donc constituée de trois axes principaux : Le premier axe vise l'élaboration d'une méthode de communication entre les deux modèles. Tout d'abord, nous décrivons une procédure de transformation automatique entre un système expert à base de règles vers un nouveau modèle de CSP dynamique nommé DDCSP (Dynamic Domain CSP) que nous avons au préalable défini. Cette procédure de transformation automatique permettra l'injection des résultats de l'un des deux modèles en entrée de l'autre. Cette procédure joue donc un rôle essentiel pour assurer la collaboration qui s'appuie sur l'échange d'informations. Le deuxième axe est consacré à la prise en compte de la distribution d'un problème CSP sur plusieurs sites. Nous proposons un algorithme basé sur la notion de coopération et de parallélisme qui assure une résolution distribuée entre plusieurs agents. Notre approche consiste à construire un anneau d'agents autonomes, responsable chacun d'une partie des variables et des contraintes du problème. Chacun de ces agents va initier un processus qui explore une branche différente de l'arbre de recherche. Des heuristiques sont proposées pour garantir une diversification des explorations, en d'autres termes pour éviter que les branches explorées ne se recouvrent. Enfin, nous présentons une technique de sécurisation de cet algorithme dans l'environnement distribué basée sur l'utilisation judicieuse des propriétés de cryptographie asymétrique pour préserver la confidentialité des instanciations. Afin d'effectuer une validation expérimentale de nos travaux, une implémentation dans les langages de programmation C/C++ ou Java est décrite dans chacun de ces trois axes. / A wide range of practical problems requires diversity of data representation and to develop models in which different data can be represented. In this thesis, we focus on the hybridization of two models: Expert System (ES) and Constraint Satisfaction Problem (CSP).The aim of our work is to propose a secure distributed system that allows integrating constraints in an inference engine.To reach this goal, on one hand we developed a communication tool that facilitates collaboration between ES and CSP. On the other hand, we designed an algorithm that allows communication between multiple entities in a distributed environment. Finally, one of our goals, not the least, is to protect private data of each entity. The thesis is composed of three main axes.The first priority is to develop a method of communication between the two models. First, we describe an automatic transformation procedure of the rule based expert system into the new dynamic CSP model called DDCSP (Dynamic Domain CSP) that we have designed. This procedure will automatically transform and inject the result of one of the two models as input to the other one. This process plays an essential role for collaboration based on the exchange of information.Our second axe proposes an algorithm based on the concept of cooperation and parallelism which provides a resolution distributed among several entities. Our approach is to build a ring of autonomous agents, each responsible for some of the variables and constraints of the problem. Each of these agents will initiate a process that explores a different branch of the search tree. Heuristics are proposed to ensure a diversification of exploration, in other words to prevent overlapping of the explored branches.Finally, we present a technique for securing this distributed algorithm based on a judicious use of the properties of asymmetric encryption to protect the confidentiality of instantiations. To perform an experimental validation of our work, an implementation in the programming languages C/C++ or Java is described in each of these three axes.

Although satisfiability problems (SAT) are NP-complete, state-of-the-art SAT solvers are able to solve large practical instances. The notion of backdoors has been introduced to capture structural properties of instances. Backdoors are a set of variables for which there exists some value assignment that leads to a polynomial-time solvable sub-problem. I address in this thesis the problem of finding all minimal backdoors, which is essential for studying value and variable ordering mistakes. I discuss our definition of sub-solvers and propose algorithms for finding backdoors. I implement our proposed algorithms by modifying a state-of-the-art SAT solver, Minisat. I analyze experimental results comparing our proposed algorithms to previous algorithms applied to random 3SAT, structured, and real-world instances. Our proposed algorithms improve over previous algorithms for finding backdoors in two ways. First, our algorithms often find smaller backdoors. Second, our algorithms often find a much larger number of backdoors.

Although satisfiability problems (SAT) are NP-complete, state-of-the-art SAT solvers are able to solve large practical instances. The notion of backdoors has been introduced to capture structural properties of instances. Backdoors are a set of variables for which there exists some value assignment that leads to a polynomial-time solvable sub-problem. I address in this thesis the problem of finding all minimal backdoors, which is essential for studying value and variable ordering mistakes. I discuss our definition of sub-solvers and propose algorithms for finding backdoors. I implement our proposed algorithms by modifying a state-of-the-art SAT solver, Minisat. I analyze experimental results comparing our proposed algorithms to previous algorithms applied to random 3SAT, structured, and real-world instances. Our proposed algorithms improve over previous algorithms for finding backdoors in two ways. First, our algorithms often find smaller backdoors. Second, our algorithms often find a much larger number of backdoors.

Le formalisme CSP (Problème de Satisfaction de Contraintes) permet de représenter de nombreux problèmes de manière simple et efficace. Cependant, une partie de ces problèmes ne peut être résolue de manière classique et centralisée. Les causes peuvent être diverses : temps de rapatriement des données prohibitif, sécurité des données non garantie, etc. Les CSP Distribués(DisCSP), domaine intersectant celui des SMA et des CSP, permettent de modéliser et de résoudre ces problèmes naturellement distribués. Les raisonnements intra-agent et inter-agents sont alors basés sur un ensemble de relations entre différentes variables. Les agents interagissent afin de construire une solution globale à partir des solutions locales. Nous proposons, dans ce travail, un algorithme de résolution de DisCSP nommé Distributed Backtracking with Sessions (DBS) permettant de résoudre des DisCSP où chaque agent dispose d’un problème local complexe. DBS a la particularité de ne pas utiliser de nogoods comme la majorité des algorithmes de résolution de DisCSP mais d’utiliser à la place des sessions. Ces sessions sont des nombres permettant d’attribuer un contexte à chaque agent ainsi qu’à chaque message échangé durant la résolution du problème. Il s’agit d’un algorithme complet permettant l’utilisation de filtres sur les messages échangés sans remettre en cause la preuvede complétude. Notre proposition est évaluée, dans les cas mono-variable et multi-variables par agents, sur différents benchmarks classiques (les problèmes de coloration de graphes distribués et les DisCSP aléatoires) ainsi que sur un problème d’exploration en environnement inconnu. / The CSP formalism (Constraint Satisfaction Problem) can represent many problems in a simple and efficient way. However, some of these problems cannot be solved in a classical and centralized way. The causes can be multiple: prohibitive repatriation time, unsecured data and so on. Distributed CSP (DisCSP), domain intersecting MAS and CSP, are used to model and to solve these problems. The intra-agent and inter-agent reasonning are so based on a set of relation between different variables. The agents interact in order to build a global solution from local solutions. We propose, in this work, an algorithm for solving DisCSP named Distributed Backtracking with Sessions (DBS) which allows to solve DisCSP where each agent owns a complex local problem. DBS has the particularity to not use nogoods like the majority of algorithms for solvingDisCSP but to use instead of sessions. These sessions are numbers which allow to assign a context to each agent and each message exchanged during the resolution of the problem. DBS is a complete algorithm which allows the use of filters on messages exchanged without affecting the proof of completeness. Our proposal is evaluated, for mono-variable and multi-variables per agents problems, on different classical benchmarks (distributed graph coloring problems and random DisCSP) and on an unknown environment exploration problem.

Concentrated Solar Power (CSP) also known as concentrated solar thermal is the systematic act of using mirrors and lenses to concentrate direct sunlight to a specific focal point so that solar radiation can be converted into useful electrical energy. The genesis of CSP technology dates back from the 1800s, when August Mouchout used a Parabolic Trough Collector (PTC) to produce steam. CSPs are known to have different types of collector technology which include the enclosed trough, solar power tower, fresnel reflectors, dish stirling, and parabolic trough collector. It has been established that a Parabolic Trough collector (PTC) is the most developed form of technology that a concentrated solar power plant can utilize to harness the energy of the sun. PTCs are commonly used by large scale plants to collect a large amount of solar radiation and incorporate it into their many functions. PTCs are energy reactors which enables heat exchange between solar energy and a transport fluid medium. They are ‘parabolic’ in shape, consist of an absorption tube located at the focal concentrating point, a bearing structure, and a shiny reflector surface. PTCs can either have a one or two-axis tracking system. PTCs with a two-axis tracking system are more efficient because of their zero-incidence angle, however they are generally more costly to maintain and have higher thermal losses involved. It is highly imperative that the PTC reflector surface has constant good reflectance as this is where the Direct Normal Irradiance (DNI) is absorbed and emitted to the focal line of the PTC. Strict design requirements such as high UV reflectance, corrosion resistance and weather resistance are necessary. Past research has proven that aluminium is a good choice of material because of its low cost and high reflective properties. A PTC system can be applied in different areas according temperature output requirements. For lower temperature requirement (100°C- 250°C) they are used for domestic heating, heat driven refrigeration systems and air conditioning units. For higher temperature requirement (300°C- 400°C), they are used in CSP plants arranged in array form with multiple PTC units connected together ultimately forming a PTC plant. Generally, all CSP plants are located in dessert arid regions where the exposure to sunlight is hardly hindered. Maximum exposure to sunlight is necessary for a CSP plant as the solar energy that reaches the earth is about 170 trillion kWH and the major aim of all CSP plants is to harness as much as possible effectively. In this regard, the reflectivity of mirror facets of a collector unit needs to be kept clean and free of any substance that reduces reflectivity. Due to CSP plant location, dessert storms and sandstorms occur frequently causing sand particles to be deposited on the surface of mirrors. Mirror soling is defined as the deposition of dust particles on mirror facets resulting from particle movement from one region to the mirror. Dust particles can absorb and deflect solar rays that hit the mirror facets limiting reflectivity and limiting the performance output of a CSP plant. Mirror soiling is phenomena that cannot be easily prevented 100% as there are different sizes to particles and one would have to stop the weather and climate altogether. PTC plants as well as other CSP plants experience mirror soiling on a daily basis of their operation. In dealing with this problem, plants have employed cleaning methods that commonly utilize a large volume of water which gives favourable results in trying to maintain high reflectivity. However, for a location that is dry and arid, it is not economical to carry on using water where it is a considerable finite resource. To minimize water usage in handling this problem to a significant number or nil, researchers have tried automated novel methods, water saving methods and dust prevention methods. A dust prevention method that has proven to reduce mirror soiling to a significant number is the installation of a wind barrier. It has been numerically proven and validated that a wind barrier, placed in the prevailing wind direction, can deflect dust particles away from a defined mirror location. The presented thesis and research aim to re-introduce porous barriers and non-porous barriers as a simple economical practical approach that can minimize mirror soiling and present it as an alternative solution that lessens the volume of water used to clean collector facets. The thesis is purely simulation-based and incorporates particle mechanics and computational fluid dynamic (CFD) to show results and performance of wind barriers ultimately deriving an optimum candidate that can be manufactured and used in CSP plants. The study used ANSYS 2019 packages as the simulation tool to perform simulations and optimization procedures. Results showed that an optimum porous barrier has the capability to increase a CSP plant efficiency by a significant percentage. / Dissertation (MEng (Mechanical Engineering))--University of Pretoria, 2021. / Mechanical and Aeronautical Engineering / MEng (Mechanical Engineering) / Unrestricted

<p>In this thesis we examine the computational complexity of determining the satisfaction of various Mal'cev conditions. First we present a novel classification of linear idempotent Mal'cev conditions based on the form of the equations with which they are represented. Using this classification we present a class of conditions which can be detected in polynomial time when examining idempotent algebras. Next we generalize an existing result of Freese and Valeriote by presenting another class of conditions whose satisfaction is exponential time hard to detect in the general case, and en route we prove that it is equally hard to detect local constant terms. The final new contribution is an extension of a recent result of Maróti to a subclass class of weak Mal'cev conditions, proving that their detection is decidable and providing a rough upperbound for the complexity of the provided algorithm for said detection. We close the thesis by reviewing the current state of knowledge with respect to determining satisfaction of linear idempotent Mal'cev conditions.</p> / Doctor of Philosophy (PhD)

Seawater desalination plays an important role when fighting the freshwater scarcity that many places around the world are currently facing. The increasing need for desalinated water is followed by a high energy demand. It is therefore essential that an expansion of desalination capacity is accompanied by a parallel use of renewable energy sources in this process. This thesis presents a techno-economic study on a reverse osmosis (RO) desalination plant, with a nominal power consumption of 15 MW, that is powered by a concentrated solar power (CSP) plant combined with a photovoltaic (PV) power plant, in Kuwait. The main aim of this thesis was to find which system designs would give the lowest global warming potential and levelized cost of the desalinated water. In addition, it has been investigated how electricity price and emission allowance cost could make a solar power plant competitive to the grid. For this purpose, some components in the whole system were simulated using System Advisor Model and Engineering Equation Solver. With the results obtained from the simulations, a dynamic model of the whole system was developed in MATLAB, Simulink where simulations were done for a typical meteorological year in Shagaya, Kuwait. Both on-grid and off-grid systems were considered.   In the on-grid case, the lowest cost of water was obtained with only PV (ca 0.65 USD/m3) and this could reduce carbon emissions by 30 % compared to only using the grid. Combining CSP and PV could reduce the carbon emissions by 85 % but with a 35 % increase in water cost. It was found that an electricity price of 0.1 USD/kWh or an emission allowance cost of 70 USD/tCO2-eq would make a CSP + PV plant competitive to the grid. These results indicate that the choice of which system is best for powering an on-grid RO plant depends on how the environmental and economic factors are prioritised. In the case of the off-grid system, both the lowest cost of water (ca 0.9 USD/m3) and the highest capacity factor were obtained with a CSP + PV plant with 16 h of storage, a solar multiple of 3 and a PV capacity of 28 MW.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-08-08T12:10:14Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) v_final_assinaturas_branco.pdf: 10378086 bytes, checksum: 35e52eff52531ee36b6a5af5b2a20645 (MD5) / Made available in DSpace on 2016-08-08T12:10:14Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) v_final_assinaturas_branco.pdf: 10378086 bytes, checksum: 35e52eff52531ee36b6a5af5b2a20645 (MD5) Previous issue date: 2016-03-03 / The increasing complexity of systems has led to increasing difficulty in design. Thestandard approach to development, based on trial and error, with testing used at later stages toidentify errors, is costly and leads to unpredictable delivery times. In addition, for critical systems,for which safety is a major concern, early verification and validation (V&V) is recognised asa valuable approach to promote dependability. In this context, we identify three important anddesirable features of a V&V technique: (i) a graphical modelling language; (ii) formal andrigorous reasoning, and (iii) automated support for modelling and reasoning. We address these points with a refinement technique for SysML supported by tools. SysML is a UML-based language for systems design; it has itself become a de facto standard in the area. There is wide availability of tool support from vendors like IBM, Atego, and Sparx Systems. Our work is distinctive in two ways: a semantics for refinement and for a representative collection of elements from the UML4SysML profile (blocks, state machines, activities, and interactions) used in combination. We provide a means to analyse design models specified using SysML. This facilitates the discovery of problems earlier in the system development lifecycle, reducing time and costs of production. In this work we describe our semantics, which is defined using a state-rich process algebra called CML and implemented in a tool for automatic generation of formal models. We also show how the semantics can be used for refinement-based analysis and development. Our case studies are a leadership-election protocol, a critical component of an industrial application, and a dwarf signal, a device used to control rail traffic. Our contributions are: a set of guidelines that provide meaning to the different modelling elements of SysML used during the design of systems; the individual formal semantics for SysML activities, blocks and interactions; an integrated semantics that combines these semantics with another defined for state machines; and a framework for reasoning using refinement about systems specified by collections of SysML diagrams. / O aumento da complexidade dos sistemas tem levado a um aumento na dificuldade da atividade de projeto. A abordagem padrão para desenvolvimento, baseada em tentativa e erro, com testes usados em estágios avançados para identificar erros, é custosa e leva a prazos de entrega imprevisíveis. Além disto, para sistemas críticos, para os quais segurança é um conceito chave, Verificação e Validação (V&V) com antecedência é reconhecida como uma abordagem valiosa para promover confiança. Neste contexto, nós identificamos três características importantes e desejáveis de uma técnica de V&V: (i) uma linguagem de modelagem gráfica; (ii) raciocínio formal e rigoroso, e (iii) suporte automático para modelagem e raciocínio. Nós tratamos estes pontos com uma técnica de refinamento para SysML apoiada por ferramentas. SysML é uma linguagem baseada na UML para o projeto de sistemas. Ela tem se tornado um padrão de facto na área. Há uma grande disponibilidade de ferramentas de fornecedores como IBM, Atego, e Sparx Systems. Nosso trabalho se destaca de duas maneiras: ao fornecer uma semântica para refinamento e considerar uma coleção representativa de elementos do perfil UML4SysML (blocos, máquina de estados, atividades, e interações) usados de forma combinada. Nós fornecemos uma estratégia para analisar modelos de projeto especificados em SysML. Isto facilita a descoberta de problemas mais cedo durante o ciclo de vida de desenvolvimento de sistemas, reduzindo tempo e custos de produção. Neste trabalho nós descrevemos nossa semântica a qual é definida usando uma álgebra de processo rica em estado chamada CML e implementada em uma ferramenta para geração automática de modelos formais. Nós também mostramos como esta semântica pode ser usada para análise baseada em refinamento. Nossos estudos de caso são um protocolo de eleição de líder, o qual é um componente crítico de uma aplicação industrial, e um sinal anão, o qual é um dispositivo para controlar tráfego em linhas férreas. Nossas contribuições são: um conjunto de orientações que fornecem significado para os diferentes elementos de modelagem de SysML usados durante o projeto de sistemas; as semânticas formais individuais para atividades, blocos e interações de SysML; uma semântica integrada que combina estas semânticas com outra definida para máquina de estados; e um arcabouço que usa refinamento para raciocínio de sistemas especificados por coleções de diagramas SysML.