Optimisation combinatoire dans les réseaux de fonctions de coût

Informations générales
Nom
Givry
Prénom
Simon
Diplôme
HDR
Année
2011
Détails de la thèse/HDR
Université
Jury
Christian Bessière
Yves Deville
Christophe Gonzales
Martin Cooper
Hélène Fargier
Christophe Lecoutre
Christian Bessière
Yves Deville
Martin Cooper
Hélène Fargier
Christophe Lecoutre
Christian Bessière
Yves Deville
Christophe Gonzales
Martin Cooper
Hélène Fargier
Christophe Lecoutre
Résumé en français
Le cadre des réseaux de fonctions de coût pose le problème de trouver une affectation d'un ensemble de variables discrètes minimisant la somme de fonctions à valeurs positives appliquées sur des sous-ensembles de ces variables. Ce problème très général, classé NP-difficile, a de multiples applications en Intelligence Artificielle, en Recherche Opérationnelle et en particulier en bio-informatique. Pour traiter ce problème de manière exacte, il est toujours possible de se ramener à des formalismes existants, par exemple la programmation linéaire en nombres entiers ou la programmation par contraintes. Cependant lorsque les fonctions du problème à résoudre ne sont ni linéaires ni associées à une sémantique particulière bien étudiée, il est alors intéressant de développer des méthodes génériques capables de travailler directement sur le réseau de fonctions de coût.
Pour cela, l'idée est d'effectuer des opérations de reformulation du réseau en un réseau équivalent mais plus simple, offrant naturellement des coupes et des heuristiques pour guider un algorithme de séparation et évaluation. Nous présentons différentes opérations de reformulation de complexité polynômiale appliquées de manière chaotique, planifiée ou optimale. Ce travail contribue à adapter les cohérences locales, et en particulier l'arc-cohérence, développées dans le cadre des problèmes de satisfaction de contraintes au cadre plus général de l'optimisation sous contraintes. L'objectif visé est d'étendre les outils de programmation par contraintes pour traiter directement les réseaux de fonctions de coût. Une plate-forme expérimentale nommée toulbar2 a été développée dans ce sens. Des résultats expérimentaux montrent les bonnes performances de l'approche sur des benchmarks réputés difficiles d'allocation de fréquence à des liens radios et sur des problèmes de correction d'erreurs Mendéliennes de génotypage.
Une autre famille de méthode repose sur la programmation dynamique non sérielle. Elle a été particulièrement étudiée dans le cadre des modèles graphiques dont font partie les réseaux de fonctions de coût. Il a été montré que lorsque le graphe primal associé à un réseau de fonctions de coût est proche d'un arbre, quitte à contracter des noeuds, le problème peut être résolu efficacement. Plus récemment, des chercheurs ont proposé d'hybrider cette approche avec un algorithme de séparation et évaluation dans le but d'être plus efficace en temps et en mémoire. Nous montrons comment utiliser au mieux les opérations de reformulation dans ces approches hybrides. Une méthode unifiant plusieurs algorithmes existants est présentée. Il s'avère que cette exploitation de la structure des problèmes est assez délicate et donne de bons résultats uniquement sur des problèmes fortement modulaires.
Enfin nous donnons quelques perspectives d'application de ces techniques dans le cadre des réseaux bayésiens, la plate-forme toulbar2 ayant remporté deux compétitions (UAI 2008 et 2010) dans ce domaine. Des opérations de reformulation spécifiques pour ces problèmes sont introduites. Nous ouvrons également le champ d'application des techniques présentées pour traiter d'autres requêtes telles que l'inférence probabiliste exacte ou approchée et l'apprentissage automatique de la structure d'un réseau bayésien.