Hybridation de méthodes complètes et incomplètes pour la résolution de CSP

Par : Lambert Tony

Document archivé le : 18/12/2007

L'hybridation des mécanismes de méthodes incomplètes et des techniques de programmation par contraintes est souvent basée sur des combinaisons de type maître-esclave, dédiées à la résolution de classes de probèmes sécifiques. Dans cette thèse, nous nous intéressons à la définition d'un modèle théorique uniforme, basé sur les itérations chaotiques de K.R. Apt qui définissent un cadre mathématique pour l'itération d'un ensemble fini de fonctions sur des domaines abstraits munis d'un ordre partiel. Ce cadre permet de prendre en compte une hybridation entre les méthodes incomplètes et les méthodes complètes. Dans ce contexte, la résolution s'apparenteà un calcul de point fixe d'un ensemble de fonctions de réductions spécifiques. Notre cadre générique permet alors d'envisager des stratégies de combinaisons et d'hybridation de manière plus fine et d'étudier leurs propriétés. Nous avons employé un cadre général approprié pour modéliser la résolution des problèmes d'optimisation et nous présentons des résultats expérimentaux qui mettent en avant les atouts de telles combinaisons en regard d'une utilisation indépendante des techniques de résolution.


Fichier(s) associé(s) au document :
pdfNatif.pdf