Dans le cadre de la Programmation par Contraintes, les contraintes globales ont amené une évolution majeure tant du point de vue modélisation (en synthétisant des ensembles de contraintes) que du point de vue résolution (grâce à des techniques de filtrage héritées d'autres domaines, comme la Recherche Opérationnelle ou l'Intelligence Artificielle). Par ailleurs, beaucoup de problèmes réels sont sur-contraints (ils ne possèdent pas de solution). Dans ce cas, il est nécessaire de relaxer certaines contraintes. De nombreuses études ont été menées pour traiter le cas des contraintes unaires et binaires, mais très peu pour le cas des contraintes globales. Dans cette thèse, nous étudions la relaxation des contraintes globales dans un cadre permettant l'expression de préférences. Pour plusieurs contraintes globales parmi les plus utilisées (c'est-à-dire AllDifferent, Gcc et Regular), nous proposons différentes sémantiques de violation ainsi que des algorithmes permettant de tester l'existence d'une solution et d'éliminer les valeurs incohérentes (filtrage). Les résultats de cette thèse ont été appliqués avec succès à des problèmes de création d'emplois du temps pour des infirmières, qui sont des problèmes sur-contraints difficiles à modéliser et surtout à résoudre. Mots-clefs : programmation par contraintes, contrainte globale, problème sur-contraints, relaxation de contraintes, contrainte globale relaxée, problème de création d'emplois du temps pour des infirmières.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-01016976 |
| Date | 09 April 2010 |
| Creators | Metivier, Jean-Philippe |
| Publisher | Université de Caen |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0017 seconds