Information: this page is not translated in english

2013-05-31 De la réduction polynomiale à la décomposition de contraintes : vers une rationalisation de la résolution des problèmes NP-complets

31 mai 2013 -- 14h30, salle E.324 : Olivier Bailleux -- Université de Bourgogne
De la réduction polynomiale à la décomposition de contraintes : vers une rationalisation de la résolution des problèmes NP-complets
Un solveur pour les résoudre tous. L’idée est séduisante. Elle s’appuie sur la notion théorique de réduction polynomiale dans une perspective pratique : réutiliser un solveur dédié à un problème cible pour résoudre d’autres problèmes sans avoir à développer des solveurs spécifiques. Cette approche pose de nombreuses questions : quels problèmes sources peuvent être résolus via un problème cible donné ? Existe-t-il un problème cible « universel » ? Comment choisir le meilleur modèle de traduction d’un problème source à un problème cible donnés ? Comment caractériser un « bon » modèle de traduction ? Le cadre de la programmation par contraintes permet-il d’aborder cette problématique sans perte de généralité ? J’aborderai toutes ces questions au regard de l’état des connaissances dans les domaines concernés et je proposerai quelques pistes de recherches.

Last update on 18/06/2013