Déterminer si un problème de satisfaction de contraintes (CSP) a une solution ou non est NP-complet. Les CSP sont résolus par inférence (c’est-à-dire, en appliquant un algorithme de cohérence), par énumération (c’est-à-dire en effectuant une recherche avec retour sur trace ou backtracking), ou, plus souvent, en intercalant les deux mécanismes. La propriété de cohérence la plus courante appliquée en cours du backtracking est la GAC (Generalized Arc Consistency). Au cours des dernières années, de nouveaux algorithmes pour appliquer des cohérences plus fortes que le GAC ont été proposés et montrés comme étant nécessaires pour résoudre les problèmes difficiles.Nous nous attaquons à la question de balancer d’une part le coût et, d’autre part, le pouvoir d’élagage des algorithmes de cohérence et posons cette question comme étant celle de déterminer où, quand et combien une cohérence doit-elle être appliquée en cours de backtracking. Pour répondre à la question « où », nous exploitons la structure topologique d'une instance du problème et focalisons la cohérence forte là où des structures cycliques apparaissent. Pour répondre à la question « quand », nous proposons une stratégie simple, réactive et efficace qui surveille la performance du backtracking puis déclenche une cohérence forte lorsque l’effort du retour sur trace devient alarmant. Enfin, pour la question du « combien », nous surveillons les mises à jour provoquées par la propagation des contraintes et interrompons le processus dès qu’il devient inactif ou coûteux même avant qu’il n’atteigne un point fixe. Les évaluations empiriques sur des problèmes de référence établissent l’efficacité de nos stratégies. / Determining whether or not a Constraint Satisfaction Problem (CSP) has a solution is NP-complete. CSPs are solved by inference (i.e., enforcing consistency), conditioning (i.e., doing search), or, more commonly, by interleaving the two mechanisms. The most common consistency property enforced during search is Generalized Arc Consistency (GAC). In recent years, new algorithms that enforceconsistency properties stronger than GAC have been proposed and shown to be necessary to solve difficult problem instances.We frame the question of balancing the cost and the pruning effectiveness of consistency algorithms as the question of determining where, when, and how much of a higher-level consistency to enforce during search. To answer the ‘where’ question, we exploit the topological structure of a problem instance and target high-level consistency where cycle structures appear. To answer the ‘when’ question, we propose a simple, reactive, and effective strategy that monitors the performance of backtrack search and triggers a higher-level consistency as search thrashes. Lastly, for the question of ‘how much,’ we monitor the amount of updates caused by propagation and interrupt the process before it reaches a fixpoint. Empirical evaluations on benchmark problems demonstrate the effectiveness of our strategies.

La thèse porte sur la résolution des problèmes de satisfiabilité propositionnelle (SAT) et des problèmesde satisfaction de contraintes (CSP). Ces deux modèles déclaratifs sont largement utilisés pour résoudredes problèmes combinatoires de première importance comme la vérification formelle de matérielset de logiciels, la bioinformatique, la cryptographie, la planification et l’ordonnancement de tâches.Plusieurs contributions sont apportées dans cette thèse. Elles vont de la proposition de schémas d’hybridationdes méthodes complètes et incomplètes, répondant ainsi à un challenge ouvert depuis 1998, àla résolution parallèle sur architecture multi-coeurs, en passant par l’amélioration des stratégies de résolution.Cette dernière contribution a été primée à la dernière conférence internationale du domaine (prixdu meilleur papier). Ce travail de thèse a donné lieu à plusieurs outils (open sources) de résolution desproblèmes SAT et CSP, compétitifs au niveau international. / This thesis deals with propositional satisfiability (SAT) and constraint satisfaction problems(CSP). These two declarative models are widely used for solving several combinatorial problems (e.g.formal verification of hardware and software, bioinformatics, cryptography, planning, scheduling, etc.).The first contribution of this thesis concerns the proposition of hybridization schemes of complete andincomplete methods, giving rise to an original answer to a well-known challenge open since 1998. Secondly,a new and efficient multi-core parallel approach is proposed. In the third contribution, a novelapproach for improving clause learning management database is designed. This contribution allows spatialcomplexity reduction of the resolution-based component of SAT solvers while maintaining relevantconstraints. This contribution was awarded at the last international SAT conference (best paper award).This work has led to several open sources solving tools for both propositional satisfiability and constraintssatisfaction problems.

Plusieurs paradigmes de programmation existent pour aider à résoudre des problèmes d'optimisation combinatoire, l'un d'entre eux étant la programmation par contraintes. L'idée de ce paradigme consiste à modéliser le problème à résoudre à l'aide de contraintes, c'est-à-dire des déclarations qui forcent les variables du problème à respecter une relation mathématique. Les contraintes des problèmes ont habituellement des paramètres qui permettent de préciser la relation mathématique à respecter et des variables de décision qui représentent les variables pour lesquelles la relation mathématique doit s'appliquer. Bien qu'intéressant en soi, la programmation par contraintes peut également s'étendre sur d'autres concepts, notamment la modélisation automatique. L'acquisition ou apprentissage de contraintes consiste à apprendre les différentes contraintes, incluant les valeurs des paramètres, qui peuvent expliquer un ensemble d'exemples fournis. L'apprentissage de contraintes peut être utile dans plusieurs situations, comme l'apprentissage de structures d'horaires d'hôpitaux à l'aide d'anciens exemples d'horaires. L'apprentissage de contraintes est encore un domaine nouveau pour lequel les stratégies doivent encore être adaptées ou développées. Les techniques d'acquisition existantes varient en genre, incluant des méthodes qui créent des solutions artificielles pour interagir avec un utilisateur ou des approches qui se basent sur des analyses mathématiques rigoureuses de solutions pour faire des choix sans jamais communiquer avec l'utilisateur. Dans ce mémoire, nous explorons une nouvelle méthode pour performer l'acquisition de contraintes. Le critère principal de la méthode développée est basé sur le nombre de solutions du modèle considéré et utilise des outils de dénombrement. Notre technique performe bien sur les problèmes essayés et ouvre la porte à une nouvelle manière d'apprivoiser les problèmes d'acquisition de contraintes. / Several programming paradigms exist to help solve combinatorial optimization problems, one of them being constraint programming. The idea of this paradigm is to model the problems to solve using constraints, i.e. statements that force the variables of the problem to respect a mathematical relation. The constraints of a problem usually have parameters that allow to specify the mathematical relationship to be respected and decision variables that represent the variables on which the mathematical relationship must be applied. Although interesting in itself, constraint programming can also expand on other concepts, such as the automatisation of the modeling process. Constraints acquisition consists in learning the different constraints, including parameter values, which can explain a set of examples provided. Constraint acquisition can be useful in multiple situations, such as learning structures in schedules for hospitals using old schedules. Constraint learning is still a new area for which strategies still need to be adapted or developed. The existing techniques of acquisition varies widely in style, including methods that create artificial solutions to interact with a user or approaches which are based on complex mathematical analyzes of real solutions to make choices without ever communicating with the user. In this thesis, we explore a new method to perform the acquisition of constraints. The main criterion of the developed method is based on the number of solutions of the considered model and uses tools of model counting. Our technique works well on proven problems and opens the door to a new way of approaching acquisition constraint problems.

Ce mémoire porte sur le problème de décision CSP (de l'anglais Constraint Satisfaction Problem, c'est-à-dire problème de satisfaction de contraintes), soit le problème pour lequel nous devons assigner des valeurs à des variables de telle sorte que toutes les conditions portant sur ces variables soient remplies. De surcroît, ce mémoire porte sur les problèmes de détection d'homomorphisme entre structures relationelles qui sont équivalents à CSP. Pour être plus précis, nous nous intéressons à l'algorithme de cohérence d'arc pour les instances de CSP, soit ArcjConsistency. Celui-ci suffit à solutionner un certain sous-ensemble de CSP. Or nous étudions quelques-unes de ses variantes qui sont des algorithmes plus coûteux, mais plus puissants, c'est-à-dire que le sous-ensemble de CSP qu'ils solutionnent est plus grand. La nouveauté de ce mémoire est de décrire et d'étudier une variante de ArcjConsistency, soit NLjCohérence, qui est un algorithme moins puissant mais plus efficace. L'objectif pour nous est de trouver des caractéristiques intéressantes au sujet de ce nouvel algorithme, qui se veut être une version « espace logarithmique » de ArcjConsistency. De plus, nous travaillons sur un sous-ensemble de CSP dit implicatif. Nous démontrons que NL_Cohérence solutionne les instances de ce sous-ensemble en espace logarithmique non-déterministe.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Notre étude porte sur les transporteurs ABC dans les génomes bactériens complets. L'analyse bioinformatique du répertoire de ces systèmes comprend l'identification des partenaires, l'assemblage, la reconstruction des systèmes incomplets, la classification en sous-familles, et l'identification du substrat transporté. Cette thèse propose des outils permettant l'étude de ces problèmes par l'utilisation de méthodes informatiques. Les hypothèses biologiques employées sont que : (i) des gènes voisins sur le chromosome peuvent être impliqués dans un même processus métabolique s'ils ont été conservés au cours de l'évolution, et (ii) des gènes présentant des similarités de séquence peuvent permettre la synthèse de protéines de même fonction. Trois études ont été menées sur le répertoire des transporteurs ABC : * L'exploration du voisinage chromosomique. D'après l'hypothèse selon laquelle plus les gènes conservés dans le voisinage d'un transporteur sont proches, plus leur lien fonctionnel avec le transporteur est fort, on essaye d'identifier le substrat transporté ou des associations de gènes. Ce problème est traité par une méthode de résolution issue des problèmes de satisfaction de contraintes. * La classification. Les transporteurs ABC sont classés par grandes catégories en fonction des molécules qu'ils transportent (sucres, ...). Pour chaque domaine, en représentant les relations d'homologie par un graphe, la recherche des zones de forte densité permet de déterminer des sous-classes de substrat. * La reconstitution des systèmes incomplets. Les transporteurs ABC sont assemblés en utilisant la proximité chromosomique des gènes codant pour les domaines et la compatibilité des sous-familles de domaines. Lorsque la proximité n'est pas respectée, on utilise une stratégie développée à partir d'une méthode d'analyse de graphes pour assembler les domaines et prédire des systèmes actifs. Ces méthodes, en complément de l'identification des partenaires et de l'assemblage, permettent une étude fonctionnelle des transporteurs ABC. Elles pourraient être appliquées à d'autres systèmes biologiques.

Cette thèse traite de l'utilisation des algorithmes évolutionnaires (AE) pour résoudre des problèmes de satisfaction de contrainte (CSP) en domaines finis sans spécialisation ni hybridation particulière. Après avoir présenté les CSP et les méthodes couramment utilisées pour les résoudre (chapitres 1 et 2), nous présentons le paradigme évolutionnaire et ses applications (chapitres 3 et 4). Ensuite, nous proposons une comparaison entre les méthodes de recherche arborescente et les métaheuristiques sur des coloriages de graphe sur-contraints, dans un contexte de réglage des paramètres minimal (chapitre 5). Nous étudions le paysage de recherche pour comprendre les raisons des différences d'efficacité des méthodes. Enfin, nous proposons de nouveaux opérateurs génétiques (croisement, mutation, diversification) dont le paramétrage est moins fastidieux qu'avec les opérateurs classiques (chapitre 6). Nous concluons sur l'intérêt d'exploration des réseaux de neutralité.

Les problèmes d'optimisation et de satisfaction de contraintes sur des ensembles de variables discrètes sont l'objet principal de la complexité algorithmique. Ces problèmes ont récemment bénéficié des outils et des concepts de la physique des systèmes désordonnés, à la fois théoriquement et algorithmiquement. En particulier, il a été suggéré que les difficultés pratiques soulevées par certaines instances dures de problèmes d'optimisation sont liées à la structure fragmentée de leur espace de solutions, qui rappelle une phase vitreuse. Parallèlement, les codes de correction d'erreur de pointe, qui peuvent être ramenés à des problèmes d'optimisation, reposent sur la séparabilité de leurs messages afin d'assurer une communication fiable. L'objet de cette thèse est d'explorer, dans un cadre commun, cette relation entre les propriétés d'inférence et l'organisation géométrique, dans les problèmes issus de la complexité algorithmique et de la théorie de l'information.<br /><br />Après une introduction physique des problèmes et des concepts liés aux domaines sus-évoqués, les méthodes de passage de messages, basées sur l'approximation de Bethe, sont introduites. Ces méthodes sont utiles d'un point de vue physique, car elle permettent d'étudier les propriétés thermodynamiques d'ensemble d'instances aléatoires. Elles sont également utiles pour l'inférence. L'analyse de spectres de distances est ensuite effectuée à l'aide de méthodes combinatoires et de passage de messages, et mises à profit afin de prouver et l'existence de la fragmentation dans les problèmes de satisfaction de contraintes, et d'en étudier les aspects importants.

Le planificateur temporel IxTeT, véritable «intelligence embarquée» d'un robot autonome, s'appuie sur un gestionnaire de contraintes temporelles dont le rôle est double: maintenir la cohérence du réseau de contraintes, et répondre rapidement et correctement à une interrogation émanant du planificateur. La prise en compte de contraintes symboliques (simples précédences) et numériques (dates et durées imprécises) oblige alors à une propagation coûteuse des contraintes numériques. Néanmoins, ces dernières étant proportionnellement peu nombreuses en planification, nous pouvons restreindre cette propagation à un sous-graphe numérique. Par ailleurs, nous devons tenir compte en planification de durées «contingentes», dont la valeur est aléatoire. Ces incertitudes nous obligent à redéfinir la notion classique de cohérence, et à nous ramener à un modèle temporel dual, appelé Graphe de Décision, dans lequel nous pouvons utiliser les algorithmes classiques de propagation. Le mémoire s'achève par la présentation d'une application distincte relevant du domaine de l'ordonnancement de tâches pour un ensemble de robots. L'incertitude pesant sur les contraintes numériques oblige ici à allouer les ressources au fur et à mesure de l'exécution. Les caractéristiques propres à l'application suggèrent une décomposition du graphe temporel conduisant à une efficacité optimale des algorithmes de propagation

Cette thèse se situe dans le contexte de la programmation par contraintes (CP). Plus précisément, nous nous sommes intéressés au problème de satisfaction de contraintes pondérées (WCSP). De nombreuses approches ont été proposées pour traiter ce problème d’optimisation. Les méthodes les plus efficaces utilisent des cohérences locales souples sophistiquées comme par exemple la cohérence d’arc directionnelle complète FDAC∗, la cohérence d’arc directionnelle existentielle EDAC∗, etc. Établies grâce à des opérations de transferts de coût préservant l’équivalence des réseaux, l’utilisation de ces cohérences permet généralement d’accélérer la résolution en réduisant l’espace de recherche via la suppression de valeurs et le calcul de bornes inférieures utiles en pratique. Cependant, l’utilisation de ces méthodes pose un problème lorsque l’arité des contraintes augmente de manière significative. L’efficacité des techniques du cadre du problème de satisfaction de contraintes (CSP) étant avérée, nous pensons que l’intégration de techniques CSP peut être très utile à la résolution d’instances WCSP. Dans cette thèse, nous proposons tout d’abord un algorithme de filtrage établissant la cohérence d’arc souple généralisée GAC∗ sur des contraintes tables souples de grande arité. Cette approche combine la technique de réduction tabulaire simple (STR), issue du cadre CSP, et le principe de transfert de coûts. Notre approche qui est polynomiale calcule efficacement pour chaque valeur les coûts minimaux dans les tuples explicites et implicites des contraintes tables souples. Ces coûts minimaux sont ensuite utilisés pour transférer les coûts afin d’établir GAC∗. Dans un second temps, nous proposons une approche alternative aux méthodes de résolution habituelles du problème WCSP. Elle consiste à résoudre une instance WCSP en résolvant une séquence d’instances CSP classiques obtenues depuis cette instance WCSP. À partir d’une instance CSP dans laquelle toutes les contraintes de l’instanceWCSP d’origine sont durcies au maximum, les instances CSP suivantes correspondent à un relâchement progressif de contraintes de l’instance WCSP déterminées par l’extraction de noyaux insatisfaisables minimaux (MUC) depuis les réseaux insatisfaisables de la séquence. Nos résultats expérimentaux montrent que notre première approche est compétitive avec l’état de l’art, tandis que la deuxième représente une approche alternative aux méthodes de résolutionhabituelles d’instances WCSP. / This thesis is in the context of constraint programming (CP). Specifically, we are interested in the Weighted Constraint Satisfaction Problem (WCSP). Many approaches have been proposed to handle this optimization problem. The most effective methods use sophisticated soft local consistencies such as, for example, full directional arc consistency FDAC∗, existential directional arc consistency EDAC∗, etc. Established by equivalence preserving transformations (cost transfer operations), the use of these consistencies generally allows both to accelerate the resolution by reducing the search space through the elimination of values and to compute lower bounds useful in practice. However, these methods reach theirlimits when the arity of constraints increases significantly. The techniques of the Constraint Satisfaction Problem framework (CSP) having proved efficienty, we believe that the integration of CSP techniques can be very useful for solving WCSP instances. In this thesis, we first propose a filtering algorithm to enforce a soft version of generalized arc consistency (GAC∗) on soft table constraints of large arity. This approach combines the techniques of simple tabular reduction (STR), from the CSP framework, with the techniques of cost transfer. Our approach, proved polynomial, efficiently calculates for each value the minimum cost of the explicit and implicit tuples from soft table constraints. The minimum costs are thenused to transfer costs to establish GAC∗. In a second step, we propose an alternative approach to the usual techniques to solve WCSP. The principle is to solve a WCSP instance by solving a sequence of classical CSP instances obtained from this WCSP instance. From a CSP instance containing all the constraints hardened to the maximum from the WCSP instance, the next CSP instances correspond to a progressive relaxation of constraints defined by extraction of minimal unsatisfiable cores (MUC) from unsatisfiable networks of the sequence. Our experimental results show that our first approach is competitive with the state-of-the-art, whereas the second one represents an alternative approach to the usual methods to solve WCSP instances.