Anciens Axes

• Optimisation dans les graphes
  Axe 3. Graphes et optimisation dans les graphes
  M.-C. Costa, C. Picouleau, F. Roupin, D. de Werra, C. Bentz, N. Derhy, H. Topart, E. Soutif, B. Robillard
  

  Multichemins, multiflots entiers et multicoupes

  Ce thème concerne la recherche de multicoupes et multiflots en nombres entiers de valeur maximale dans un graphe. Les arêtes du graphe étant munies de capacité et/ou de coûts, trouver un multiflot entier maximal consiste à router une quantité maximale de flots entre k paires de sommets appelés sources (S₁, S₂,...S_k) et puits (T₁, T₂,.., T_k). Si les demandes pour chaque couple (S_k, T_k) sont fixées, on recherche le routage de coût minimal. Trouver une multicoupe minimale consiste à sélectionner un ensemble d’arêtes de poids minimal coupant tous les chemins reliant une source S_k à un puits T_k. Nous avons obtenu plusieurs résultats intéressants sur ces problèmes qui sont très difficiles en nombres entiers [CLR05]. En particulier, nous avons résolu polynomialement par des approches primales-duales le problème sur certaines grilles [BCR05, BCR07] ainsi que sur les anneaux [BCL09] qui sont très utilisés dans les réseaux. Ce dernier résultat est surprenant puisque de nombreux problèmes de même type sont NP-difficiles sur les anneaux. Nous avons également obtenu des résultats concernant la recherche d’une (multi)coupe minimale sous contrainte de cardinalité en considérant un ou plusieurs critères [BCD06, BCD09]. En particulier, nous avons montré que le problème ouvert de s-t coupe minimale, soumise à cette contrainte, était fortement NP-difficile. Les thèses de Cédric Bentz et Nicolas Dérhy sont dans ce premier thème de l’axe 3.

  Graphes et complexité

  En collaboration avec l’EPFL de Lausanne nous avons étudié le problème de la coloration d’un nombre minimal d’arêtes assurant l’existence de couplages colorés de cardinal fixé [CWP07]. Nous avons également abordé la recherche de d-transversaux (intersectant tous les couplages optimaux en au moins d arêtes) et de d-bloqueurs (dont la suppression diminue d’au moins d la cardinalité d’un couplage maximal) [ZRP09]. Enfin nous avons étudié le problème de l’algorithmique on-line pour la recherche de certains sous-graphes [DKS05], (Thèse de Bernard Kouakou).

  Tomographie discrète et graphes

  Nous avons mis en évidence certains liens existant entre des problèmes de tomographie discrète et des problèmes de recherche de structures particulières ou de reconstruction de graphes. Le problème de reconstruction de tableaux colorés nous a conduit à l'étude de problèmes de graphes faisant intervenir des couplages ou plus généralement des b-couplages, différentes colorations généralisant les colorations usuelles des sommets ou des arêtes, les séquences de degrés des sommets. Des résultats de complexité algorithmique ainsi que diverses propriétés ont été démontrés [CWP06].

  Arbres couvrant induits

  Le problème de Steiner est l'un des problèmes de l'optimisation combinatoire les plus étudiés depuis plusieurs décennies en raison notamment de son intérêt théorique et des ses nombreuses applications. Nous avons étudié ce problème en ajoutant une contrainte supplémentaire imposant que la solution trouvée forme un arbre induit. Nous avons prouvé des résultats de complexité pour différents sous-problèmes et variations de ce problème [DP09]. Nous nous sommes également intéressés à la classe des graphes sans triangles pour laquelle nous avons obtenu des résultats structurels et algorithmiques [DPT09]. (Thèse de Nicolas Dérhy).

  Réseaux robustes

  Nous avons mis en évidence une nouvelle classe de graphes, les « hypotriangulés » qui ont la caractéristique d’être robustes pour la défection d’un nœud ou d’une arête tout en conservant les distances des plus courts chemins entre deux sommets non adjacents. Nous avons caractérisé la structure de ces graphes et étudié la complexité de certains problèmes classiques dans cette classe [CPT09]. (Thèse d’Hélène Topart).

  Application 1 : collaboration avec l’équipe CPR autour de la conception d’un compilateur certifié et optimisé

  Il s’agit d’une collaboration entre les équipes CPR et OC du Cédric, qui a pour but de mettre à profit les compétences de ces deux équipes afin de réaliser un compilateur certifié et optimisé. Ce projet transverse prolonge dans sa partie optimisation le projet ANR Compcert, qui vise à concevoir un compilateur de langage C vérifié formellement. Le problème étudié ici est l’allocation de registres du processeur. Il s’agit de l’une des phases de la compilation devant être optimisées. Plus spécifiquement, nous nous intéressons à un problème de coloration avec préférences dans les graphes triangulés. Nous avons obtenus des résultats théoriques sur la complexité de ce problème particulier et mis en œuvre des algorithmes de résolution que nous avons en partie vérifiés formellement [BRS08], [BRS08b], [BRS07]. (Thèse de Benoît Robillard).

  Application 2 : collaboration avec l’équipe SemPia autour du placement de capteurs dans les réseaux point à point

  En collaboration avec l'équipe SemPia et EDF (Grenoble) nous avons étudié le placement de capteurs à installer le long d'une conduite forcée [CFH07]. Nous avons montré que le problème se ramène dans certains cas à la recherche de chemins disjoints de coût minimal ou à des problèmes de multiflots. (Stage de Ted Hardy). Nous avons également proposé un premier modèle mathématique pour le problème général. Dans la suite de ce travail, nous avons collaboré à un projet ANR (Verso, Réseaux du futur) concernant la mise en place de réseaux sans fil pour la sécurité des musées. Ce projet implique aussi 2 PME, 2 musées, les Pompiers de Paris et la direction des musées de France. Le projet a obtenu le label Cap-Digital mais n’a pas été accepté. Il sera modifié et représenté.

   

  
  
• Axe 2. Tomographie discrète et application
  C. Picouleau, M. C. Costa, D. de Werra, F. Jarray
  
  Tomographie
  

  La tomographie discrète ou reconstruction d’images discrètes à partir de certaines  de leurs projections est un sujet en pleine expansion. Ses applications  industrielles en cristallographie et en imagerie médicale font de ce sujet une  source importante de problèmes algorithmiques.

  Nous avons en particulier traité le placement de barres sous des contraintes  de non adjacence, le pavage par dominos et la reconstruction de matrices binaires sous diverses contraintes [BCF07] [CJP08] [CJP08b] [CJP05].

  Nous nous intéressons également au problème de reconstruction d'un tableau tricolore. Ce problème vient d’être prouvé NP-complet. Nous avons mis en évidence certains cas polynomiaux. Nous avons mis en avant des liens étroits existant entre la tomographie discrète et certains problèmes de la théorie des graphes [BCW08, CWP09]. Des algorithmes et des  résultats de complexité ont été obtenus pour ces différents sujets [BFP08, CWP08].

  Application à la planification d’horaires de travail

  Certains problèmes de planification de personnel se modélisent comme des  problèmes de tomographie discrète. C'est le cas de l'affectation de jours de repos  à des employés connaissant le nombre de jours total de repos dévolus à chaque  employé sur l'horizon de planification et le nombre d'employés nécessaires chaque jour à la bonne marche de l'entreprise. Nous avons montré que de  nombreux cas peuvent être résolus polynomialement à l'aide d’algorithmes issus  de la théorie des graphes et de la tomographie discrète [CJP08].