Les heuristiques de recherche locale sont connues depuis longtemps pour être extrêmement efficaces en pratique. Récemment, des avancées majeures ont montré que l'on pouvait également obtenir de bonnes garanties théoriques dans certains cas. De tels algorithmes sont en général très faciles à implémenter, dès qu'une façon pertinente de modifier une solution localement a été définie. Ils peuvent être esquissés comme suit : Partir d'une solution (non optimale) ; Explorer toutes les solutions qui peuvent être obtenues de celle-ci par une petite modification (par exemple, l'ajout ou la suppression d'un sommet) ; Choisir une ``meilleure'' nouvelle solution (de façon déterministe ou probabiliste) ; Répéter jusqu'à ce qu'une solution raisonnable soit atteinte. Cette approche soulève de nombreuses questions théoriques importantes. Peut-on explorer ainsi l'espace tout entier des solutions ? De façon équivalente, dans le modèle probabiliste, si on voit l'algorithme comme une chaîne de Markov, est-elle ergodique ? Se mélange-t-elle rapidement ? (En d'autres termes, toute solution peut-elle être atteinte avec probabilité raisonnable en un nombre raisonnable d'étapes ?)

Ces questions peuvent être vues sous l'angle plus général de la reconfiguration combinatoire. Au lieu de chercher une solution pour une instance donnée, supposons qu'une solution est déjà en place. Certains aspects de l'instance (objectif, contraintes...) peuvent évoluer avec le temps, surtout dans un environnement dynamique. Dans ce cas, on peut vouloir reconfigurer la solution existante en une nouvelle solution plus adaptée. Pour des raisons pratiques (ressources limitées....), il peut être nécessaire d'opérer cette transformation de façon graduée, sans perdre les propriétés voulues à un seul instant.

La faisabilité et d'autres aspects de telles transformations étape par étape ont été au coeur des travaux autour de la Reconfiguration Combinatoire. Ces problèmes ont reçu une attention croissante cette dernière décennie. Trois questions apparaissent naturellement lorsqu'on considère des problèmes de reconfiguration combinatoire :

  • Quelles modifications élémentaires garantissent que toute solution admissible soit transformable en n'importe quelle autre ?
  • Combien d'étapes sont nécessaires pour une telle transformation ?
  • Peut-on trouver une (courte) transformation efficacement ?

Ces questions sont les problèmes fondamentaux en théorie de la reconfiguration combinatoire. Les questions de reconfiguration sont fortement liées à d'autres domaines d'informatique fondamentale. Dans ce projet, nous nous concentrons particulièrement sur les :

  • Aspects structurels ;
  • Aspects algorithmiques, notamment algorithmes polynomiaux, FPT et d'approximation ;
  • Conséquences pour l'énumération ;
  • Applications pour l'échantillonage.

Les liens entre ces sujets de recherche et la reconfiguration seront détaillés tout au long du projet, comme les application de la reconfiguration à d'autres domaines tels que la physique statistique ou la chimie. Le projet sera organisé en cinq Groupes de Travail (WP). Ces groupes de travail sont transverses aux sujets de recherche, dans le sens où les objectifs de chaque groupe de travail requièrent des compétences variées pour être atteints.

L'équipe a été mise au point dans un esprit de complémentarité des compétences qui nous permettra de nous attaquer à tous les aspects de la reconfiguration. Au cours du projet, nous prévoyons également d'organiser un workshop international et une école d'été, afin de de développer cette branche en France et tout spécialement auprès des jeunes chercheurs.