<a> Sujet du stage </a>
Nous nous intéressons ici au partitionnement d'un graphe représentant une zone géographique, par exemple une région viticole. Les différentes parcelles de vigne possèdent des caractéristiques propres qui conditionnent la qualité et le type de raisins à mettre en place sur chaque parcelle. De plus, un traitement spécifique est à prévoir pour chacune des parcelles de même type. Il est alors nécessaire de répartir les parcelles en zones ayant le même type de vigne et de traitement. Chacune de ces zones doit rester connexe, c'est à dire que l'on peut passer d'une parcelle à l'autre de la zone sans sortir de la zone. On peut construire un graphe où chaque parcelle est un sommet et où une arête relie deux parcelles contiguës. Le problème est alors nommé partitionnement connexe d'un graphe.
Un tel partitionnement de graphe trouve de nombreuses applications dans des domaines très variés : la répartition de ressources en télécommunications, la recherche de motifs en analyse d'images, l'aide à la décision médicale... De nombreuses approches théoriques et algorithmiques ont été étudiées pour ce problème.<br><br>
Certains cas particuliers peuvent être résolus efficacement (par exemple le problème de la coupe minimum), mais de manière générale ces problèmes sont NP-difficiles (comme le problème de la coupe maximum). L'objectif est de résoudre ce problème de partitionnement en zones géographiques connexe pour des instances réalistes.<br><br>
<a> Objectifs du stage</a>
L'étude et la résolution de ce problème de partitionnement seront menées en utilisant les formulations linéaires en nombres entiers et plus particulièrement par approche polyédrale. Cette approche, issue de la programmation mathématique, s'est révélée efficace dans la conception de méthodes de résolution de problèmes d'optimisation combinatoire réputés difficiles (problème de la coupe maximum, problème du voyageur de commerce).<br><br>
Le stage débutera par une étude bibliographique qui permettra au stagiaire de se familiariser avec les techniques abordées dans ce stage. L'objectif sera ensuite d'étudier la structure combinatoire du problème de partitionnement en composantes connexes et son lien avec les problèmes de multi-coupes. En particulier, nous nous intéresserons à la structure polyédrale de l'enveloppe convexe des solutions associées au problème de $k$-partitionnement en composantes connexes. Les résultats obtenus seront ensuite utilisés dans l'élaboration d'un algorithme de coupes et branchements (branch-and-cut). Une autre approche est de considérer une décomposition de Dantzig-Wolfe menant à un algorithme de génération de colonnes (branch-and-price), chaque colonne représentant une composante connexe. Le sous-problème générant les colonnes consiste alors à chercher un sous-graphe induit connexe de coût minimum dans un graphe. Une étude polyédrale et algorithmique du sous-problème pourra alors être menée.<br><br>
Les algorithmes développés seront testés sur des instances réalistes issues de la littérature.<br><br>
<a>Cadre du stage</a>
Ce stage s'inscrit dans une collaboration avec le Laboratoire d'Informatique de Paris-Nord et l'Institut de Mathématique de l'Université de Bordeaux. Plusieurs directions de recherche ont dors et déjà été établies. Le stagiaire, en accord avec son encadrant, pourra ainsi choisir une de ces pistes (ou en proposer de nouvelles) parmi l'étude de plusieurs formulations et techniques de mises en oeuvre.<br><br>