La programmation par contraintes intègre des algorithmes de résolution génériques dans des langages de modélisation déclaratifs basés sur les contraintes : ces langages permettent de décrire des problèmes combinatoires sous la forme d’un ensemble de variables devant prendre leurs valeurs dans des domaines en satisfaisant des contraintes. Nous introduisons dans cette thèse un algorithme de résolution générique paramétré par : — une stratégie d’exploration de l’espace de recherche, à choisir parmi, chronological backtracking, conflict directed backjumping, conflict directed backjumping with reordering, dynamic backtracking, decision repair, et backtracking with tree decomposition ; — une heuristique de choix de variables, à choisir parmi, min-domain/ddeg et min-domain/wdeg ; — une technique de propagation de contraintes, à choisir parmi, forward checking et maintaining arc consistency. Ainsi, cet algorithme générique s’instancie en vingt-quatre configurations différentes ; certaines correspondant à des algorithmes connus, d’autres étant nouvelles. Ces vingt- quatre configurations ont été comparées expérimentalement sur un benchmark de plus de mille instances, chaque configuration étant exécutée plusieurs fois sur chaque instance pour tenir compte du non déterminisme des exécutions. Des tests statistiques sont utilisés pour comparer les performances. Cette évaluation expérimentale a permis de mieux comprendre la complémentarité des différents mécanismes de résolution, avec une attention particulière portée sur la capacité à tirer parti de la structure des instances pour accélérer la résolution. Nous identifions notamment treize configurations complémentaires telles que chaque instance de notre benchmark est bien résolue par au moins une des treize configurations. Une deuxième contribution de la thèse est d’introduire un sélecteur capable de choisir automatiquement la meilleure configuration de notre algorithme générique pour chaque nouvelle instance à résoudre : nous décrivons chaque instance par un ensemble de descripteurs et nous utilisons des techniques d’apprentissage automatique pour construire un modèle de choix de configuration à partir de ces descripteurs. Sachant que l’apprentissage est généralement plus difficile quand il y a beaucoup de configurations, nous exprimons le problème du choix du sous-ensemble de configurations pouvant être sélectionnées comme un problème de couverture d’ensemble et nous comparons deux critères de choix : le premier vise à maximiser le nombre d’instances résolues par au moins une configuration et le second vise à maximiser le nombre d’instances pour lesquelles il y a une bonne configuration disponible. Nous montrons expérimentalement que la seconde stratégie obtient généralement de meilleurs résultats, et que le sélecteur obtient de meilleures performances que chacune de nos vingt-quatre configurations initiales. / Constraint programming integrates generic solving algorithms within declarative languages based on constraints : these languages allow us to describe combinatorial problems as a set of variables which have to take their values in domains while satisfying constraints. Numerous real-life problems can be modelled in such a way, as for instance, planification problems, scheduling problems, . . . These problems are NP-complete in the general case of finite domains. We introduce in this work a generic solving algorithm parameterized by : — a strategy for exploring the search space, to be chosen from the following six, chronological backtracking, conflict directed backjumping, conflict directed backjumping with reordering, dynamic backtracking, decision repair, and backtracking with tree decomposition ; — a variable ordering heuristic, to be chosen from the following two, min-domain/ddeg and min-domain/wdeg ; — a constraint propagation technique, to be chosen from the following two, forward checking and maintaining arc consistency. Thus, this algorithm leads to 24 different configurations ; some corresponding to already known algorithms, others being new. These 24 configurations have been com- pared experimentally on a benchmark of more than a thousand instances, each configuration being executed several times to take into account the non-determinism of the executions, and a statistical test has been used to compare performances. This experimental evaluation allowed us to better understand the complementarity of the different solving mechanisms, with a focus on the ability to exploit the structure of the instances to speed up the solving process. We identify 13 complementary configurations such that every instance of our benchmark is well solved by at least one of the 13 configurations. A second contribution of this work is to introduce a selector able to choose automatically the best configuration of our generic solver for each new instance to be solved : we describe each instance by a set of features and we use machine learning techniques to build a model to choose a configuration based on these features. Knowing that the learning process is generally harder when there are many configurations to choose from, we state the problem of choosing a subset of configurations that can be picked as a set covering problem and we compare two criterion : the first one aims to maximize the number of instances solved by at least one configuration and the second one aims to maximize the number of instances for which there is a good configuration available. We show experimentally that the second strategy obtains generally better results and that the selector obtains better performances than each of the 24 initial configurations.

Cette thèse se place dans le contexte de l'hébergement de services informatiques virtualisés et apporte deux contributions. Elle propose premièrement un système d'aide à la gestion modulaire, déplaçant les machines virtuelles du centre pour le maintenir dans un état satisfaisant. Ce système permet en particulier d'intégrer la notion de consommation électrique des serveurs ainsi que des règles propres à cette consommation. Sa modularité permet de plus l'adaptation de ses composants à des problèmes de grande taille. Cette thèse propose de plus un outil pour comparer différents gestionnaires de centres virtualisés. Cet outil injecte un scénario de montée en charge reproductible dans une infrastructure virtualisée. L'injection d'un tel scénario permet d'évaluer les performances du système de gestion du centre grâce à des sondes spécifiques. Le langage utilisé pour cette injection est extensible et permet l'utilisation de scénarios paramétrés.

Cette thèse se place dans le contexte de l’hébergement de services informatiques virtualisés et apporte deux contributions. Elle propose premièrement un système d’aide à la gestion modulaire, déplaçant les machines virtuelles du centre pour le maintenir dans un état satisfaisant. Ce système permet en particulier d’intégrer la notion de consommation électrique des serveurs ainsi que des règles propres à cette consommation. Sa modularité permet de plus l’adaptation de ses composants à des problèmes de grande taille. Cette thèse propose de plus un outil pour comparer différents gestionnaires de centres virtualisés. Cet outil injecte un scénario de montée en charge reproductible dans une infrastructure virtualisée. L’injection d’un tel scénario permet d’évaluer les performances du système de gestion du centre grâce à des sondes spécifiques. Le langage utilisé pour cette injection est extensible et permet l’utilisation de scénarios paramétrés. / This thesis considers the virtualized IT services hosting and makes two contributions. It first proposes a modular system of management aids, to move the virtual machines of the center in order to keep it in a good condition. This system allows in particular to integrate the concept of server power consumption and rules specific to that concept. What’s more, its modularity allows to adjust its components to handle larger problems. This thesis proposes also a tool to compare different virtualized centers managers. This tool injects a reproductible load increase scenario in a virtualized infrastructure. The injection of such a scenario is used to evaluate the performance of the system center manager, using performances probes. The language used for this injection is extensible and allows the creation of parameterized scenarios. The contributions of this thesis were presented in two international conferences and a french conference.