The notion that a universally effective problem solver may still exist, and is simply waiting to be found, is slowly being abandoned in the light of a growing body of work reporting on the narrow applicability of individual heuristics. As the formalism of the constraint satisfaction problem remains a popular choice for the representation of problems to be solved algorithmically, there exists an ongoing need for new algorithms to effciently handle the disparate range of problems that have been posed in this representation. Given the costs associated with manually applying human algorithm development and problem solving expertise, methods that can automatically adapt to the particular features of a specific class of problem have begun to attract more attention. Whilst a number of authors have developed adaptive systems, the field, and particularly with respect to their application to constraint satisfaction problems, has seen only limited discussion as to what features are desirable for an adaptive constraint system. This may well have been a limiting factor with previous implementations, which have exhibited only subsets of the five features identified in this work as important to the utility of an adaptive constraint satisfaction system. Whether an adaptive system exhibits these features depends on both the chosen represen-tation and the method of adaptation. In this thesis, a three-part representation for constraint algorithms is introduced, which defines an algorithm in terms of contention, preference and selection functions. An adaptive system based on genetic programming is presented that adapts constraint algorithms described using the mentioned three-part representation. This is believed to be the first use of standard genetic programming for learning constraint algo-rithms. Finally, to further demonstrate the efficacy of this adaptive system, its performance in learning specialised algorithms for hard, real-world problem instances is thoroughly evaluated. These instances include random as well as structured instances from known-hard benchmark distributions, industrial problems (specifically, SAT-translated planning and cryptographic problems) as well as over-constrained problem instances. The outcome of this evaluation is a set of new algorithms - valuable in their own right - specifically tailored to these problem classes. Partial results of this work have appeared in the following publications: [1] Stuart Bain, John Thornton, and Abdul Sattar (2004) Evolving algorithms for constraint satisfaction. In Proc. of the 2004 Congress on Evolutionary Computation, pages 265-272. [2] Stuart Bain, John Thornton, and Abdul Sattar (2004) Methods of automatic algorithm generation. In Proc. of the 9th Pacific Rim Conference on AI, pages 144-153. [3] Stuart Bain, John Thornton, and Abdul Sattar. (2005) A comparison of evolutionary methods for the discovery of local search heuristics. In Australian Conference on Artificial Intelligence: AI'05, pages 1068-1074. [4] Stuart Bain, John Thornton, and Abdul Sattar (2005) Evolving variable-ordering heuristics for constrained optimisation. In Principles and Practice of Constraint Programming: CP'05, pages 732-736.

Temporal reasoning has been an active research area for over twenty years, with most work focussing on either enhancing the efficiency of current temporal reasoning algorithms or enriching the existing algebras. However, there has been little research into handling over-constrained temporal problems except to recognise that a problem is over-constrained and then to terminate. As many real-world temporal reasoning problems are inherently over-constrained, particularly in the scheduling domain, there is a significant need for approaches that can handle over-constrained situations. In this thesis, we propose two backtracking algorithms to gain partial solutions to over-constrained temporal problems. We also propose a new representation, the end-point ordering model, to allow the use of local search algorithms for temporal reasoning. Using this model we propose a constraint weighting local search algorithm as well as tabu and random-restart algorithms to gain partial solutions to over-constrained temporal problems. Specifically, the contributions of this thesis are: The introduction and empirical evaluation of two backtracking algorithms to solve over-constrained temporal problems. We provide two backtracking algorithms to close the gap in current temporal research to solve over-constrained problems; The representation of temporal constraint networks using the end-point ordering model. As current representation models are not suited for local search algorithms, we develop a new model such that local search can be applied efficiently to temporal reasoning; The development of a constraint weighting local search algorithm for under-constrained problems. As constraint weighting has proven to be efficient for solving many CSP problems, we implement a constraint weighting algorithm to solve under-constrained temporal problems; An empirical evaluation of constraint weighting local search against traditional backtracking algorithms. We compare the results of a constraint weighting algorithm with traditional backtracking approaches and find that in many cases constraint weighting has superior performance; The development of a constraint weighting local search, tabu search and random-restart local search algorithm for over-constrained temporal problems. We extend our constraint weighting algorithm to solve under-constrained temporal problems as well as implement two other popular local search algorithms: tabu search and random-restart; An empirical evaluation of all three local search algorithms against the two backtracking algorithms. We compare the results of all three local search algorithms with our twobacktracking algorithms for solving over-constrained temporal reasoning problems and find that local search proves to be considerably superior.

<p>The need for debugging tools for declarative programming languages has increased due to the rapid development of modeling and simulation tools/programs. Declarative equation-based programming languages have the problem of equation systems being over-, or under-constrained. This means that the system of equations has more equations than variables or more variables than equations respectively, making the system of equations unsolvable. In this study a static debugger is implemented in OpenModelica compiler for the equation-based programming language Modelica to make it easier for the programmer or modeler to locate the equation/s causing the unconstrained system of equations. The debugging techniques used by the debugger are developed by Peter Bunus. Those techniques are able to detect unconstrained systems of equations and give solutions by identifying the minimal set ofequation/s that should be removed or which variable/s should be added to an equation/s to make the system solvable. In this study the debugging techniques for detecting and giving a solution for over-constrained system of equations are shown suitable to be used for the programming language Modelica in the OpenModelica compiler.</p>

The need for debugging tools for declarative programming languages has increased due to the rapid development of modeling and simulation tools/programs. Declarative equation-based programming languages have the problem of equation systems being over-, or under-constrained. This means that the system of equations has more equations than variables or more variables than equations respectively, making the system of equations unsolvable. In this study a static debugger is implemented in OpenModelica compiler for the equation-based programming language Modelica to make it easier for the programmer or modeler to locate the equation/s causing the unconstrained system of equations. The debugging techniques used by the debugger are developed by Peter Bunus. Those techniques are able to detect unconstrained systems of equations and give solutions by identifying the minimal set ofequation/s that should be removed or which variable/s should be added to an equation/s to make the system solvable. In this study the debugging techniques for detecting and giving a solution for over-constrained system of equations are shown suitable to be used for the programming language Modelica in the OpenModelica compiler.

La programmation par contraintes est une approche intéressante pour traiter des problèmes d’ordonnancement. En ordonnancement cumulatif, les activités sont définies par leur date de début, leur durée et la quantité de ressource nécessaire à leur exécution. La ressource totale disponible (la capacité) en chaque instant est fixe. La contrainte globale Cumulative modélise ce problème en programmation par contraintes. Dans de nombreux cas pratiques, la date limite de fin d’un projet est fixée et ne peut être retardée. Dans ce cas, il n’est pas toujours possible de trouver un ordonnancement des activités qui n’engendre aucun dépassement de la capacité en ressource. On peut alors tolérer de relâcher la contrainte de capacité, dans une limite raisonnable, pour obtenir une solution. Nous proposons une nouvelle contrainte globale : la contrainte SoftCumulative qui étend la contrainte Cumulative pour prendre en compte ces dépassements de capacité. Nous illustrons son pouvoir de modélisation sur plusieurs problèmes pratiques, et présentons différents algorithmes de filtrage. Nous adaptons notamment les algorithmes de balayage et d’Edge-Finding à la contrainte SoftCumulative. Nous montrons également que certains problèmes pratiques nécessitent d’imposer des violations de capacité pour satisfaire des règles métiers, modélisées par des contraintes additionnelles. Nous présentons une procédure de filtrage originale pour traiter ces dépassements imposés. Nous complétons notre étude par une approche par décomposition. Enfin, nous testons et validons nos différentes techniques de résolution par une série d’expériences. / Constraint programming is an interesting approach to solve scheduling problems. In cumulative scheduling, activities are defined by their starting date, their duration and the amount of resource necessary for their execution. The total available resource at each point in time (the capacity) is fixed. In constraint programming, the Cumulative global constraint models this problem. In several practical cases, the deadline of theproject is fixed and can not be delayed. In this case, it is not always possible to find a schedule that does not lead to an overload of the resource capacity. It can be tolerated to relax the capacity constraint, in a reasonable limit, to obtain a solution. We propose a new global constraint : the SoftCumulative constraint that extends the Cumulative constraint to handle these overloads. We illustrate its modeling power on several practical problems, and we present various filtering algorithms. In particular, we adapt the sweep and Edge-Finding algorithms to the SoftCumulative constraint. We also show that some practical problems require to impose overloads to satisfy business rules, modelled by additional constraints. We present an original filtering procedure to deal with these imposed overloads. We complete our study by an approach by decomposition. At last, we test and validate our different resolution techniques through a series of experiments.

Un système de solides peut être classé suivant trois états de mobilité: l’état non assemblé, l’état assemblé rigide et l’état assemblé mobile. L’étude se focalise sur les systèmes de solides sur-contraints en boucle fermée. Lors de l’étape de conception ou reconception, les dimensions d’un système de solides sur-contraints sont amenées à être modifiées, ce qui peut avoir pour conséquence la perte de son état de mobilité.L’approche présentée dans cette thèse a pour but de proposer une assistance au concepteur lors du redimensionnement, lui permettant de modifier ou conserver l’état de mobilité d’un système de solides. Le redimensionnement de systèmes de solides sur-contraints nécessite la connaissance de relations dépendant de leurs dimensions: les équations d’assemblage et les conditions de mobilité. Ces relations sont obtenues à l’aide d’un outil de résolution algébrique: les bases de Gröbner. La résolution algébrique est parfois coûteuse, voire impossible en un temps raisonnable, c’est ce qui justifie les méthodes décrites dans cette thèse.La solution proposée est composée de deux étapes principales. Tout d’abord, les représentations algébriques d’un système de solides fermé et mobile sont décrites. Les équations de fermeture d’un système de solides composé de plusieurs boucles sont obtenues en utilisant un paramétrage en coordonnées relatives. Les équations de mobilité sont elles générées à partir des équations de fermeture, à l’aide de méthodes directes ou incrémentales. Ensuite, afin de faciliter la génération des équations d’assemblage et de mobilité, une analyse algébrique reposant sur des outils d’analyse numérique est définie. L’état de mobilité du système de solides à redimensionner est déterminé à partir d’un ensemble de valeurs des paramètres le décrivant. Si le concepteur souhaite modifier l’état de mobilité du système de solides, de nouvelles valeurs sont alors générées. Lorsque l’état de mobilité souhaité est obtenu, il est possible de varier les dimensions tout en conservant cet état. Pour cela, certaines dimensions sont spécialisées afin de faciliter la génération des équations d’assemblage et des conditions de mobilité. Si les paramètres choisis sont liés ou trop nombreux, l’analyse mène inéluctablement à une absence de solutions. Des stratégies de partitionnement pour pallier ces problèmes sont aussi proposées. Enfin, les outils développés dans le logiciel Maple® afin d’illustrer les différents concepts proposés sont présentés, et un outil interactif permettant au concepteur de naviguer sur les équations de fermeture, équations d’assemblage et les conditions de mobilité obtenues après spécialisation, est proposé. / An assembly can be partitioned into three mobility states: the impossible state, the rigid state and the mobile state. The study focuses in over-constrained closed-loop assemblies. During the process of design or re-design, the dimensions of the assembly can vary and this can lead to the loss of its mobility state.The method presented in this thesis aims at helping the designer to resize an assembly. There exist relationships between the dimension of the assembly that ensure the closure and the mobility of over-constrained. These relationships called assembly equations and mobility conditions are hence necessary to resize an over-constrained solid assembly. Assembly equations and mobility conditions are computed by a computer algebra tool: Gröbner bases. However, the algebraic solving using Gröbner bases can be costly and may fail because of unreasonable computing time, this is the main reason of the strategies described in this thesis.The approach proposed in this thesis is composed of two main steps. First of all, an algebraic representation of a closed assembly and a mobile assembly is descibed. The closed-loop equations are written by using a coordinate free method and the mobility equations are generated from the closed-loop equations using direct and incremental methods. To simplify the computation of assembly equations and mobility conditions an algebraic analysis that rely on numerical analysis tools is proposed. Starting from a set of values of the parameters that describe the assembly to resize, the mobility state of the assembly is determined. Then, if the designer want to change the mobility state, a new set of values that have the mobility state chosen by the designer is generated. Once the initial set of values has the right mobility state, some dimensions are specialized to ease the computation of assembly equations and mobility conditions. However, if the parameters chosen are linked or its number is to high, there is a high chance that the study lead to no solution. Strategies to avoid these problems are also proposed. Finally, the tools developped in Maple® software that illustrate the methods proposed are described and an interactive tool that permits the designer to visualize the solutions of the closed-loop equations, assembly equations and mobility conditions computed after specialisation is proposed.

Due to modularity and easy scalability, modular multilevel converters (MMCs) are deemed the most suitable for high-voltage and medium-voltage power conversion applications. However, large module capacitors are usually required in MMCs to store large circulating power of line-frequency and its harmonics that flow through the capacitors. Even though several methods for minimizing the circulating power have been proposed in the literature, there is still the need for a systematic and simplified approach of addressing these control strategies and evaluating their efficacy. Moreover, the generally accepted feedback control architecture for the MMC is complicated, derived through a rigorous mathematical analysis, and therefore, not easy to intuitively comprehend. Recently, a method of modeling of the MMC based on state-plane analysis and coordinate transformation, is proposed in the literature. Based on the state-plane analysis, two kinds of circulating power in the MMC are identified that are orthogonal to each other. This means these two circulating power can be controlled individually without affecting each other. To control these circulating power, in the literature, a decoupled equivalent circuit model is developed through the coordinate transformation which clearly suggests a means for minimizing these circulating power. Further extending this work, in this thesis, the existing control concepts for reducing the circulating power are unveiled in a systematic and simplified manner utilizing the decoupled equivalent circuit model. A graphical visualization of circulating power using the state-planes is provided for each control strategy to readily compare its efficacy. Moreover, the generally accepted control architecture of the MMC is presented in an intuitive and simplified way using the decoupled circuit model. The important physics related to control implementation, originally hidden behind the complicated mathematics, is explained in detail. / Master of Science / A power converter is an electrical device that converts electrical energy from one form to another in order to be compatible with the load demand. A typical power converter consists of semiconductor switches, inductor, capacitor etc. These power converters are required in a wide range of applications: automotive and traction, motor drives, renewable energy conversion, energy storage, aircraft, power generation, transmission, and distribution, to name a few. Many of these applications are continuously increasing their power capacity to handle the escalating demands of energy that exist due to rising population numbers, industrialization, urbanization etc. Consequently, it has been a responsibility of power electronics engineers and researchers to develop power converters that can handle high voltages and high currents. Multilevel power converters have been the key-enabling developments that can withstand high-voltages while using traditional low-voltage semiconductor switches. Several multilevel converters such as the neutral point clamped converter, flying capacitor converter, cascaded H-bridge converter, modular multilevel converter (MMC) etc. have been developed and commercialized in the last two decades. Among them, the MMC is a widely accepted topology for medium- and high-voltage power conversion applications. In an MMC, several modules are stacked together in series, and each module consists of semiconductor switches and a capacitor. The series connection of the modules enables the MMC to handle high-voltage power conversion using low-voltage traditional semiconductor switches. The voltage rating of an MMC can be easily scaled-up by simply increasing the number of modules in each arm. Moreover, since several identical modules are connected in each arm, the structure of the MMC is highly modular which helps greatly in manufacturing and design. Nonetheless, in MMCs, generally large circulating power flow to the capacitor in each module, which leads to significant voltage ripples. To suppress these voltage ripples, a large capacitor is required in each module, leading to large size and weight of the converter. In the literature, several control strategies have been proposed to minimize the circulating power. However, there is still the need for a systematic and simplified approach of addressing these control strategies and evaluating their efficacy. Moreover, the generally accepted feedback control architecture for the MMC is complicated, derived through a rigorous mathematical analysis, and therefore, not easy to intuitively comprehend. Recently, a decoupled equivalent circuit model has been developed in the literature. This model clearly explains the process of power flow in the MMC between input and output and the nature of the circulating power. The equivalent circuit model provides the circulating power, that are orthogonal to each other, meaning they can be controlled individually without affecting each other. Moreover, the equivalent circuit model clearly suggests a means for minimize the circulating power by providing two "ideal" control laws. Further extending this work, in this thesis, the existing control concepts for reducing the circulating power are unveiled in a systematic and simplified manner utilizing the decoupled equivalent circuit model. Moreover, the generally accepted control architecture of the MMC is presented in an intuitive and simplified way via the decoupled circuit model. The important physics related to control implementation, originally hidden behind the complicated mathematics, is explained in detail.

Les mécanismes hyperstatiques sont souvent utilisés dans l’industrie pour garantir une bonne tenue mécanique du système et une bonne robustesse aux écarts de fabrication des surfaces. Même si ces assemblages sont très courants, les méthodologies d’analyse de tolérances de ces mécanismes sont difficiles à mettre en oeuvre.En fonction de ses écarts de fabrication, un assemblage hyperstatique peut soit présenter des interférences de montage, soit être assemblé avec jeu. Dans ces travaux de thèse, nous avons appliqué la méthode des polytopes afin de détecter les interférences de montage. Pour un assemblage donné, le polytope résultant du mécanisme est calculé. Si ce polytope est non vide, l’assemblage ne présente pas d’interférence. Si ce polytope est vide, l’assemblage présente des interférences de montage. En fonction du résultat obtenu, deux méthodes d’analyse distinctes sont proposées.Si l’assemblage est réalisable sans interférence le polytope résultant du mécanisme permet de conclure sur sa conformité au regard de l’exigence fonctionnelle. Si l’assemblage présente des interférences de montage, une analyse prenant en compte la raideur des pièces est réalisée. Cette approche est basée sur une réduction de modèle avec des super-éléments. Elle permet de déterminer rapidement l’état d’équilibre du système après assemblage. Un effort de montage est ensuite estimé à partir de ces résultats pour conclure sur la faisabilité de l’assemblage. Si l’assemblage est déclaré réalisable, la propagation des déformations dans les pièces est caractérisée pour vérifier la conformité du système au regard de l’exigence fonctionnelle.La rapidité de mise en oeuvre de ces calculs nous permet de réaliser des analyses de tolérances statistiques par tirage de Monte Carlo pour estimer les probabilités de montage et de respect d’une Condition Fonctionnelle. / Over-constrained mechanisms are often used in industries to ensure a good mechanical strength and a good robustness to manufacturing deviations of parts. The tolerance analysis of such assemblies is difficult to implement.Indeed, depending on the geometrical deviations of parts, over-constrained mechanisms can have assembly interferences. In this work, we used the polytope method to check whether the assembly has interferences or not. For each assembly, the resulting polytope of the mechanism is computed. If it is non empty, the assembly can be performed without interference. If not, there is interferences in the assembly. According to the result, two different methods can be implemented.For an assembly without interference, the resulting polytope enables to check directly its compliance. For an assembly with interferences, a study taking into account the stiffness of the parts is undertaken. This approach uses a model reduction with super elements. It enables to compute quickly the assembly with deformation. Then, an assembly load is computed to conclude on its feasibility. Finally, the spreading of deformation through the parts is calculated to check the compliance of the mechanism.The short computational time enables to perform stochastic tolerance analyses in order to provide the rates of compliant assemblies.