Harnessing tractability in constraint satisfaction problems

Clément Carbonnel 1
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Résumé : Le problème de satisfaction de contraintes (CSP) est un problème NP-complet classique en intelligence artificielle qui a suscité un engouement important de la communauté scientifique grâce à la richesse de ses aspects pratiques et théoriques. Cependant, au fil des années un gouffre s’est creusé entre les praticiens, qui développent des méthodes exponentielles mais efficaces pour résoudre des instances industrielles, et les théoriciens qui conçoivent des algorithmes sophistiqués pour résoudre en temps polynomial certaines restrictions de CSP dont l’intérˆet pratique n’est pas avéré. Dans cette thèse nous tentons de réconcilier les deux communaut és en fournissant des méthodes polynomiales pour tester automatiquement l’appartenance d’une instance de CSP à une sélection de classes traitables majeures. Anticipant la possibilité que les instances réelles ne tombent que rarement dans ces classes traitables, nous analysons également de manière systématique la possibilité de décomposer efficacement une instance en sous-problèmes traitables en utilisant des méthodes de complexité paramétrée. Finalement, nous introduisons un cadre général pour exploiter dans les CSP les idées développées pour la kernelization, un concept fondamental de complexité paramétrée jusqu’ici peu utilisé en pratique. Ce dernier point est appuyé par des expérimentations prometteuses.
Type de document :
Thèse
Automatic Control Engineering. Institut National Polytechnique de Toulouse, 2016. English
Liste complète des métadonnées

Littérature citée [130 références]  Voir  Masquer  Télécharger

https://hal.laas.fr/tel-01444799
Contributeur : Arlette Evrard <>
Soumis le : lundi 30 janvier 2017 - 14:16:00
Dernière modification le : mercredi 28 février 2018 - 10:57:33

Fichier

Identifiants

  • HAL Id : tel-01444799, version 1

Citation

Clément Carbonnel. Harnessing tractability in constraint satisfaction problems. Automatic Control Engineering. Institut National Polytechnique de Toulouse, 2016. English. 〈tel-01444799〉

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

150