Accueil > Manifestations > Thèses et HDR > Thèses > Jean-Guillaume Fages

Jean-Guillaume Fages

Directeur de thèse

Nicolas Beldiceanu
Xavier Lorca

Résumé

Cette thèse traite de l’utilisation des graphes en programmation par contraintes, dans le but d’en améliorer la capacité de passage à l’échelle. Dans un premier temps, nous étudions la résolutions de problèmes de chemins et de cycles Hamiltoniens. Nous étudions à la fois le filtrage et les stratégies d’exploration de l’espace de recherche. Nous chercherons à nous extraire progressivement des problèmes classiquement définis sur les graphes pour exploiter ce concept sur des problèmes définis sur les entiers, voire les réels. Enfin, nous utiliserons les graphes comme support pour décomposer dynamiquement des algorithmes de filtrage. Le fil conducteur de ces travaux sera d’une part l’utilisation du concept de graphe à la base de chaque raisonnement et d’autre part, la volonté pratique d’augmenter la taille des problèmes pouvant être traités en programmation par contraintes.

Mots clés : Programmation par contraintes, théorie des graphes, recherche opérationnelle, algorithmes, intelligence artificielle.

Abstract

This PhD thesis is about the use of graphs within constraint-programming, in order to improve its scalability. First, we study the solution of Hamiltonian path and cycle problems. We investigate both filtering and search. This study starts with Hamiltonian path and cycle problems. Both filtering and search are investigated. Next, we use graph concepts over problems which are no longer defined over a graph, but integers or even reals. Finally, graphs will be used to provide generic and dynamic decomposition frameworks for global constraint filtering. The central theme in this work is the use of graph concepts at the origin of every reasoning and the practical will to increase the size of problems that can be addressed in constraint-programming.

Key Words : Constraint-Programming, Graph Theory, Operational Research, Algorithms, Artificial Intelligence.

Composition du jury

  • Christine SOLNON, Professeur, Institut National des Sciences Appliquées de Lyon, Rapporteur
  • Jean-Charles RÉGIN, Professeur, Université de Nice-Sophia Antipolis, Rapporteur
  • Christophe LECOUTRE, Professeur, Université d’Artois, Examinateur
  • Benoît ROTTEMBOURG, Directeur Associé, EURODECISION, Examinateur
  • Narendra JUSSIEN, Directeur, Télécom Lille, Examinateur
  • Nicolas BELDICEANU, Professeur, Ecole des Mines de Nantes, Directeur de thèse
  • Xavier LORCA, Maître-Assistant, Ecole des Mines de Nantes, Co-encadrant

Dernière modification : mardi 7 octobre 2014