Cette thèse se focalise sur l'étude de cohérences locales fortes afin de résoudre des problèmes d'optimisation sur des réseaux de fonctions de coûts (ou réseaux de contraintes pondérées). Ces méthodes fournissent le minorant nécessaire pour des approches de type "Séparation-Evaluation". Nous étudions dans un premier temps la cohérence d'Arc virtuelle (VAC), une des plus fortes cohérences d'arcs du domaine, qui est établie via l'établissement de la cohérence d'arc dure dans une séquence de réseaux de contraintes classiques. L'algorithme itératif pour établir VAC est amélioré via l'introduction d'une incrémentalité accrue, exploitant la cohérence d'arc dynamique. La nouvelle méthode est aussi capable de maintenir VAC efficacement pendant la recherche lorsque les réseaux de contraintes pondérées sont dynamiquement modifiés par les opérations de branchement. Dans une seconde partie, nous nous intéressons à des cohérences de domaines plus fortes, inspirées de cohérences similaires dans les réseaux de contraintes classiques (cohérence de chemin inverse, réduite ou Max-réduite). Pour chaque cohérence dure, plusieurs cohérences souples ont été proposées pour les réseaux de contraintes pondérées. Les nouvelles cohérences fournissent un minorant plus fort que celui des cohérences d'arc souples en traitant les triplets de variables connectées deux à deux par des fonctions de coûts binaires. Dans cette thèse, nous étudions les propriétés des nouvelles cohérences, les implémentons et les testons sur une variété de problèmes. / This thesis focuses on strong local consistencies for solving optimization problems in cost function networks (or weighted constraint networks). These methods provide the lower bound necessary for Branch-and-Bound search. We first study the Virtual arc consistency, one of the strongest soft arc consistencies, which is enforced by iteratively establishing hard arc consistency in a sequence of classical Constraint Networks. The algorithm enforcing VAC is improved by integrating the dynamic arc consistency to exploit its incremental behavior. The dynamic arc consistency also allows to improve VAC when maintained VAC during search by efficiently exploiting the changes caused by branching operations. Operations. Secondly, we are interested in stronger domain-based soft consistencies, inspired from similar consistencies in hard constraint networks (path inverse consistency, restricted or Max-restricted path consistencies). From each of these hard consistencies, many soft variants have been proposed for weighted constraint networks. The new consistencies provide lower bounds stronger than soft arc consistencies by processing triplets of variables connected two-by-two by binary cost functions. We have studied the properties of these new consistencies, implemented and tested them on a variety of problems.

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2. / Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem. At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed. Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2. / Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem. At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed. Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.