Exploiting Global Constraints for Search and Propagation

Cette thèse se concentre sur la Programmation par contraintes (PPC), qui est un paradigme émergent pour résoudre des problèmes complexes d'optimisation combinatoire. Les principales contributions tournent autour du filtrage des contraintes et de la recherche; les deux sont des composantes cl´e dans la résolution de problèmes complexes à travers la PPC. D'un côté, le filtrage des contraintes permet de réduire la taille de l'espace de recherche, d'autre part, la recherche définit la manière dont cet espace sera exploré. Les progrès sur ces sujets sont essentiels pour élargir l'applicabilité de CP à des problèmes réels. En ce qui concerne le filtrage des contraintes, les contributions sont les suivantes: premièrement, on propose une amélioration sur un algorithme existant de la version relaxée d'une contrainte commune qui apparaît souvent dans les problèmes d'affectation (soft gcc). L'algorithme proposé améliore en termes de complexité soit pour la cohérence, soit pour le filtrage et en termes de facilité d'implémentation. Deuxièmement, on introduit une nouvelle contrainte (soit dure soit relaxée) et les algorithmes de filtrage pour une sous-structure récurrente qui se produit dans les problèmes d'affectation des ressources hétérogènes (hierarchical gcc). Nous montrons des résultats encourageants par rapport à une d´écomposition équivalente basée sur gcc. En ce qui concerne la recherche, nous présentons tout d'abord les algorithmes pour compter le nombre de solutions pour deux importantes familles de contraintes: les contraintes sur les occurrences, par exemple, alldifferent, symmetric alldifferent et gcc, et les contraintes de séquence admissible, telles que regular. Ces algorithmes sont à la base d'une nouvelle famille d'heuristiques de recherche, centrées sur les contraintes et basées sur le d´énombrement. Ces heuristiques extraient des informations sur le nombre de solutions des contraintes, pour guider la recherche vers des parties de l'espace de recherche qui contiennent probablement un grand nombre de solutions. Les résultats expérimentaux sur huit différents problèmes montrent une performance impressionnante par rapport à l'état de l'art des heuristiques génériques. Enfin, nous expérimentons une forme forte, déjà connue, de filtrage qui est guidée par la recherche (quick shaving). Cette technique donne des résultats soit encourageants soit mauvais lorsqu'elle est appliquée aveuglément à tous les problèmes. Nous avons introduit un estimateur simple mais très efficace pour activer ou désactiver dynamiquement le quick shaving; de tests expérimentaux ont montré des résultats très prometteurs.