Scheduling problems and constraint satisfaction problems are generally known to be extremely hard. This thesis proposes a new evolutionary al- gorithm approach to solve a constrained-based scheduling problem. In this approach, variable orderings are evolved. The variable ordering serves as a parameter for the constraint solver. Its purpose is to determine the order in which variables are labelled by the solver. Hence the evolving individuals may be encoded as permutations. Therefore, our approach can be applied to a wider range of constraint satisfaction problems. Methods for generating the initial population of individuals based on the analysis of the precedence constraints graph are proposed. New genetic operators are presented and successfully applied. Our approach succeeded in finding a range of diverse schedules with the optimal makespan. Furthermore, multi-objective opti- mization was successfully attempted with the NSGA-II. 1

In the present thesis we provide compact extended formulations for a wide range of polytopes associated with the constraint satisfaction problem (CSP), monadic second order logic (MSO) on graphs, and extensions of MSO, when the given instances have bounded treewidth. We show that our extended formulations have additional useful properties, and we uncover connections between MSO and CSP. We conclude that a combination of the MSO logic, CSP and geometry provides an extensible framework for the design of compact extended formulations and parameterized algorithms for graphs of bounded treewidth. Putting our framework to use, we settle the parameterized complexity landscape for various extensions of MSO when parameterized by two important graph width parameters, namely treewidth and neighborhood diversity. We discover that the (non)linearity of the MSO extension determines the difference between fixedparameter tractability and intractability when parameterized by neighborhood diversity. Finally, we study shifted combinatorial optimization, a new nonlinear optimization framework generalizing standard combinatorial optimization, and provide initial findings from the perspective of parameterized complexity

Though economically favorable when compared to other renewable energy storage technologies, thermal energy storage systems for concentrating solar thermal power (CSP) plants require additional cost reduction measures to help transition CSP plants to the point of grid-parity. Thermocline packed bed storage is regarded as one potential low cost solution due to the single tank requirement and low cost storage media. Thus sensible heat storage (SHS) and latent heat storage (LHS) packed bed systems, which are two thermocline varieties, are frequently investigated. LHS systems can be further classified as single phase change material (PCM) systems or cascaded systems wherein multiple PCMs are employed. This study compared the performance of SHS, single PCM, and cascaded PCM direct storage systems under the conditions that may be encountered in utility-scale molten salt CSP plants operating between 565°C and 288°C. A small-scale prototype SHS packed bed system was constructed and operated for use in validating a numerical model. The drawbacks of the latent heat storage process were discussed, and cascaded systems were investigated for their potential in mitigating the issues associated with adopting a single PCM. Several cascaded PCM configurations were evaluated. The study finds that the volume fraction of each PCM and the arrangement of latent heat in a 2-PCM and a 3-PCM system influences the output of the system, both in terms of quality and quantity of energy. In addition to studying systems of hypothetical PCMs, real salt PCM systems were examined and their selection process was discussed. A preliminary economic assessment was conducted to compare the cost of SHS, single-PCM LHS, cascaded LHS, and state-of-the-art 2-tank systems. To the author's knowledge, this is the first study that compares the cost of all three thermocline packed bed systems with the 2-tank design. The SHS system is significantly lower in cost than the remaining systems, however the LHS system does show some economic benefit over the 2-tank design. If LHS systems are to be viable in the future, low cost storage media and encapsulation techniques are necessary.

One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et a!. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Moths [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are: 1. The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting. 2. The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the C SP modelling framework to include array-based domains and array-based domain use constraints. 3. The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisflability problems and with several other local search techniques. We find that no one technique dominates in all problem domains. 4. The characterisation of constraint weighting performance. Based on our empirical study we identiIS' the weighting behaviours and problem features that favour constrtt weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints. 5. The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched. 6. The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problems

Un des challenges actuels de la planification est la résolution de problèmes pour lesquels on cherche à optimiser la qualité d'une solution telle que le coût d'un plan-solution. Dans cette thèse, nous développons une méthode originale pour la planification de coût optimal dans un cadre classique non temporel et avec des actions valuées.<br /><br />Pour cela, nous utilisons une structure de longueur fixée appelée graphe de planification. L'extraction d'une solution optimale, à partir de ce graphe, est codée comme un problème de satisfaction de contraintes pondérées (WCSP). La structure spécifique des WCSP obtenus permet aux solveurs actuels de trouver, pour une longueur donnée, une solution optimale dans un graphe de planification contenant plusieurs centaines de nœuds. <br /><br />Nous présentons ensuite plusieurs méthodes pour déterminer la longueur maximale des graphes de planification nécessaire pour garantir l'obtention d'une solution de coût optimal. Ces méthodes incluent plusieurs notions universelles comme par exemple la notion d'ensembles d'actions indispensables pour lesquels toutes les solutions contiennent au moins une action de l'ensemble. <br /><br />Les résultats expérimentaux effectués montrent que l'utilisation de ces méthodes permet une diminution de 60% en moyenne de la longueur requise pour garantir l'obtention d'une solution de coût optimal. La comparaison expérimentale avec d'autres planificateurs montre que l'utilisation du graphe de planification et des CSP pondérés pour la planification optimale est possible en pratique même si elle n'est pas compétitive, en terme de temps de calcul, avec les planificateurs optimaux récents.

CONKER est un noyau de communication construit à l'aide du modèle CSP.<br /> Une application décrite à l'aide de CONKER sera composée de connecteurs<br /> qui sont les obJjets charges de la communication-synchronisation et de<br /> processus qui se chargent du traitement.<br />Chaque connecteur du noyau réalise un protocole de communication particulier <br />entre les processus "applications". Ceux-ci n'utilisent que des primitives<br /> d'envoi et de réception de messages, de manière homogène et transparente à <br />la réalisation des connecteurs qui les relient.<br />Cette caractéristique de transparence, ainsi que la possibilité d'implémenter<br /> CONKER sur un ensemble de systèmes "hôtes hétérogènes", assurent une <br />transportabilité aisée des applications en environnement multi-processeurs,<br />ou sur un réseau hétérogène.<br />De part sa conception, CONKER permet de mettre â la disposition des processus<br />applications, des types de connecteurs, construits de façon incrémentale à la<br /> demande, et utilisant pour cela, les calculs de processus issus du modèle CSP.

Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources... Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été appliquée sur deux types de problèmes. Le premier est l'affectation des fréquences (FAP) dans les réseaux de radiocommunications militaires, en particulier les problèmes proposés de 1993 (instances du projet européen CALMA) jusqu'à 2010 (instances d'un projet DGA). Le deuxième est le problème académique de k-coloration de graphes sur les instances DIMACS. La méthode a amélioré quelques meilleurs scores connus actuellement. Dans les deux problèmes nous avons traité des contraintes unaires et binaires, ainsi que des contraintes n-aires et de l'optimisation de fonction sous contraintes pour le FAP. Les principes de Tabu-NG sont généraux et elle peut s'appliquer sur d'autres CSP. Elle peut par ailleurs accueillir des heuristiques spécifiques aux problèmes, nous l'avons pratiqué sur les problèmes cités, et en ce sens nous pensons pouvoir qualifier la méthode de métaheuristique sans abuser de cette définition.

La conduite de systèmes autonomes nécessite de prendre des décisions en fonction des observations et des objectifs courants : cela implique des tâches à effectuer en ligne, avec les moyens de calcul embarqués. Cependant, il s'agit généralement de tâches combinatoires, gourmandes en temps de calcul et en espace mémoire. Réaliser ces tâches intégralement en ligne dégrade la réactivité du système ; les réaliser intégralement hors ligne, en anticipant toutes les situations possibles, nuit à son embarquabilité. Les techniques de compilation de connaissances sont susceptibles d'apporter un compromis, en déportant au maximum l'effort de calcul avant la mise en situation du système. Ces techniques consistent à traduire un problème dans un certain langage, fournissant une forme compilée de ce problème, dont la résolution est facile et la taille aussi compacte que possible. L'étape de traduction peut être très longue, mais elle n'est effectuée qu'une seule fois, hors ligne. Il existe de nombreux langages-cible de compilation, notamment le langage des diagrammes de décision binaires (BDDs), qui ont été utilisés avec succès dans divers domaines de l'intelligence artificielle, tels le model-checking, la configuration ou la planification. L'objectif de la thèse était d'étudier l'application de la compilation de connaissances à la conduite de systèmes autonomes. Nous nous sommes intéressés à des problèmes réels de planification, qui impliquent souvent des variables continues ou à grand domaine énuméré (temps ou mémoire par exemple). Nous avons orienté notre travail vers la recherche et l'étude de langages-cible de compilation assez expressifs pour permettre de représenter de tels problèmes. Dans la première partie de la thèse, nous présentons divers aspects de la compilation de connaissances ainsi qu'un état de l'art de l'utilisation de la compilation dans le domaine de la planification. Dans une seconde partie, nous étendons le cadre des BDDs aux variables réelles et énumérées, définissant le langage-cible des " interval automata " (IAs). Nous établissons la carte de compilation des IAs et de certaines restrictions des IAs, c'est-à-dire leurs propriétés de compacité et leur efficacité vis-à-vis d'opérations élémentaires. Nous décrivons des méthodes de compilation en IAs pour des problèmes exprimés sous forme de réseaux de contraintes continues. Dans une troisième partie, nous définissons le langage-cible des " set-labeled diagrams " (SDs), une autre généralisation des BDDs, permettant de représenter des IAs discrétisés. Nous établissons la carte de compilation des SDs et de certaines restrictions des SDs, et décrivons une méthode de compilation de réseaux de contraintes discrets en SDs. Nous montrons expérimentalement que l'utilisation de IAs et de SDs pour la conduite de systèmes autonomes est prometteuse.

On Computer Science research, traditionally, most efforts have been devoted to research hardness for the worst case of problems (proving NP completeness and comparing and reducing problems between them are the two most known). Artifcial Intelligence research, recently, has focused also on how some characteristics of concrete instances have dramatic effects on complexity and hardness while worst-case complexity remains the same. This has lead to focus research efforts on understanding which aspects and properties of problems or instances affect hardness, why very similar problems can require very diferent times to be solved. Research search based problems has been a substantial part of artificial intelligence research since its beginning. Big part of this research has been focused on developing faster and faster algorithms, better heuristics, new pruning techniques to solve ever harder problems. One aspect of this effort to create better solvers consists on benchmarking solver performance on selected problem sets, and, an, obviously, important part of that benchmarking is creating and defining new sets of hard problems. This two folded effort, on one hand to have at our disposal new problems, harder than previous ones, to test our solvers, and on the other hand, to obtain a deeper understanding on why such new problems are so hard, thus making easier to understand why some solvers outperform others, knowledge that can contribute towards designing and building better and faster algorithms and solvers. This work deals with designing better, that is harder and easy to generate, problems for CSP solvers, also usable for SAT solvers. In the first half of the work general concepts on hardness and CSP are introduced, including a complete description of the chosen problems for our study. This chosen problems are, Random Binary CSP Problems (BCSP), Quasi-group Completion Problems (QCP), Generalised Sudoku Problems (GSP), and a newly defined problem, Edge-Matching Puzzles (GEMP). Although BCSP and QCP are already well studied problems, that is not the case with GSP and GEMP. For GSP we will define new creation methods that ensure higher hardness than standard random methods. GEMP on the other hand is a newly formalised problem, we will define it, will provide also algorithms to build easily problems of tunable hardness and study its complexity and hardness. On the second part of the work we will propose and study new methods to increase the hardness of such problems. Providing both, algorithms to build harder problems and an in-depth study of the effect of such methods on hardness, specially on resolution time.

The prominence of corporate social responsibility (CSR) initiatives today suggests that the corporate perception of such policies has shifted from an unnecessary addition to a critical business function. Using a reliable source of data on corporate social performance (CSP), this study explores and tests the relationship between CSP and corporate financial performance (CFP). Unlike prior research, this study additionally tests the impact CSP has on sales and gross margin in hopes of providing insight on sales strategies that can be implemented to maximize the impact of the relationship. The dataset includes most of the S&P 500 firms and covers years 2001-2005. The relationships are tested using time-series regressions. Results indicate that CSP and CFP have a significantly positive relationship in both directions, supporting the view that CSR programs have positive impacts on the bottom-line. Results also indicate that increased CSP leads to increases in gross margin, indicating that some customers are willing to pay a premium for the products and/or services of a company with CSR initiatives. Lastly, results also indicate that increases in CSP leads to a decrease in sales, which implies a decrease in customer base because less people are willing to buy the products at premium. Despite the result on sales, I argue in this paper that firms can increase sales by increasing CSR investments—assuming increases in CSR investments leads to higher CSP—as long as the perception of programs transform from socially responsible, philanthropic actions to programs promoting corporate shared value (CSV).