Axes

• Axe "Programmation mathématique et applications"

  Cet axe concerne essentiellement l’optimisation discrète (linéaire et non linéaire). Cette modélisation, extrêmement générale, permet de formuler de très nombreux problèmes d'optimisation combinatoire. Ces problèmes sont généralement difficiles et, dans beaucoup de cas, les problèmes de grande taille ne peuvent actuellement être résolus. Les travaux de l’équipe visent à une meilleure compréhension de ces problèmes dans le but d’améliorer leur résolution. Nous nous sommes également beaucoup intéressés à la résolution de problèmes d’optimisation industriels dans différents domaines : télécommunications, transports, énergies, environnement. Nous développons également des travaux concernant la recherche de solutions optimales robustes. Il est en effet souvent plus pertinent dans les applications industrielles de considérer une solution « robuste » qui se comportera bien dans toutes les situations susceptibles de se produire plutôt qu’une solution « optimale » pour une situation précise. L’équipe OC a déjà initié des travaux sur ce thème (2 thèses en cours) et la robustesse est source de très nombreuses problématiques.

  Résultats obtenus
  

  Optimisation quadratique. Conception de nouvelles approches de résolution des problèmes d’optimisation quadratique comportant des variables entières et éventuellement des variables réelles (un modèle très général). Ces approches ont permis d’étendre les possibilités des solveurs actuels et d’améliorer leurs performances de façon significative. Une des approches consiste à « convexifier » le problème quadratique (qui est a priori non convexe) en utilisant la programmation semi-définie. Travaux commencés avec les thèses de D. Quadri (2005) et M.-C. Plateau (2006), poursuivis avec la thèse de A. Lambert (2009)

  Programmation semi-définie appliquée à l'Optimisation Combinatoire. Des méthodes génériques ont été proposées pour construire des relaxations semi-définies et des liens entre relaxation lagrangienne et programmation semi-définie ont été mis en évidence. Ces approches ont été appliquées avec succès à la résolution de programmes quadratiques et à certains problèmes d’optimisation dans les graphes. De nouvelles approches ont également été proposées pour résoudre, avec une précision modulable, des programmes semi-définis.

  Développement durable. Dans ce domaine, deux grands types d’approches sont envisageables : la simulation et l’optimisation. La simulation est relativement simple à mettre en œuvre et a été beaucoup utilisée. L’approche optimisation est plus complexe mais, contrairement à l’approche par simulation, elle permet d’évaluer un nombre considérable d’options. Nous avons montré l’intérêt de cette approche pour la protection de la biodiversité (sélection de réserves naturelles, maîtrise des effets néfastes engendrés par la fragmentation des paysages, exploitation écologique des forêts, contrôle des espèces invasives, maintien de la diversité génétique) et l’optimisation d’un parc de production d’énergies renouvelables).

  Optimisation des réseaux télécom. Proposition de nouveaux modèles dans ce domaine et de méthodes efficaces pour les résoudre (en collaboration avec France Télécom-Orange) :

  (i) Développement d’un outil d’aide à la décision destiné au secteur opérationnel de Orange pour le développement des réseaux d’accès en fibre optique. 2 contrats CIFRE successifs (M. Trampont de 2006 à 2009 et C. Hervet depuis 2010) dont les résultats ont permis d'obtenir le « Orange Labs Award, premier prix, catégorie réseaux » en janvier 2012. Il s'agissait de résoudre un problème du type multiflots généralisés. Lors de cette étude nous avons mis au point un algorithme de génération de colonnes stabilisé par boxstep et points intérieurs. Le modèle a été affiné par des coupes et des réductions. Des instances réelles concernant la desserte de plus de mille clients ont pu être traitées.

  (ii) Optimisation des trajectoires de migration de réseaux, RTC vers VoIP (thèse CIFRE A. Le Maître 2005-2008). Il s’agit du remplacement optimal des équipements d'un réseau existant où le nombre de clients est en décroissance. Du fait de cette décroissance, il est possible de récupérer un équipement de nouvelle technologie qui n'est plus utilisé, pour le réinstaller ultérieurement. Nous avons proposé des solutions robustes qui prennent en compte l’incertitude sur les données.

  Localisation discrète. Nous avons trouvé une nouvelle formulation par la programmation linéaire en nombres entiers (PLNE) du problème p-médian (ou de localisation simple). Cette formulation tient compte de la structure de la matrice des distances entre sites pour réduire la taille du PLNE et accélérer sa résolution directe. Nous avons ensuite tiré profit de la structure du PLNE pour décrire un algorithme itératif spécifique qui réduit encore le temps de calcul. Nous avons également travaillé sur un problème nouveau de localisation de hubs pour lequel nous avons conçu une formulation par un programme quadratique en nombres entiers dont nous avons amélioré la résolution en ajoutant des inégalités valides.

  Planification robuste du matériel ferroviaire. (thèse CIFRE en cours, S. Tréfond, en collaboration avec la SNCF). La planification des engins est la détermination des enchaînements de trajets des différents engins (locomotives, rames) de façon à répondre au mieux à une certaine demande et en respectant des contraintes techniques, organisationnelles et légales. Il existe actuellement à la SNCF un logiciel qui propose une solution au problème de planification des engins en prenant en compte la couverture des trajets et les coûts d’utilisation des engins. Le but du travail de thèse est de proposer des méthodes pour déterminer des solutions qui résistent le mieux possible aux aléas (solutions robustes).

  Couvertures en nombres entiers de grande taille. Modélisation de problèmes de Planification en transport et rotation des cultures. par des programmes de couverture en nombres entiers (CIP) de grande taille. Proposition d’une nouvelle approche de résolution efficace qui fait coopérer une heuristique d’approximation garantie et la méthode de génération de colonnes. Validation expérimentale de l’approche proposée sur deux applications issues du transport ferroviaire et de la production agricole.

   

• Graphes et optimisation

   

  Axe "Graphes et optimisation"
  

  Les graphes constituent un outil mathématique fondamental de la Recherche Opérationnelle. Ils permettent la modélisation de systèmes extrêmement variés. L'obtention de solutions aux problèmes posés consiste généralement en la détection de structures optimales. De part la taille des problèmes posés la seule « puissance » des ordinateurs n'est pas suffisante pour mener à bien les calculs permettant d'obtenir une solution. Pour essayer de mener à bien cette résolution il est nécessaire de dégager des propriétés structurelles des solutions optimales pour développer, lorsque cela est possible, des algorithmes capables d'effectuer les calculs aboutissant à la résolution exacte ou approchée du problème considéré. L'axe Graphes et Optimisation a pour objectif de suivre cette démarche pour certains problèmes de graphes suffisamment généraux pour modéliser de nombreuses situations concrètes. Des travaux ont également été menés sur l’algorithmique online.

  Résultats obtenus
  

  d-bloqueurs et d-transversaux. Généralisation des notions de d-bloqueurs et de d-transversaux qui respectivement dégradent ou intersectent (d'une valeur d) toutes les solutions optimales d'un problème. Nous avons proposé un modèle général et obtenu des résultats pour divers problèmes classiques en optimisation combinatoire : chemins optimaux, coupes minimales, stables et couvertures optimales. Ces travaux ont initié des recherches menées par ou avec d'autres équipes.

  Multiflots et multicoupes. Les travaux menés au cours de la période précédente ont été continués sur ce sujet qui a de nombreuses applications. Des résultats ont été obtenus pour les graphes en anneaux et les grilles, et pour les multichemins (dans les VLSI). Les compétences acquises ont permis de travailler sur les réseaux de télécommunications en collaboration avec Orange (voir plus loin).

  Tomographie discrète et graphes. L'objectif de la tomographie discrète est de reconstruire une image à partir de ses projections, c'est-à-dire, considérant un ensemble de directions, à partir du nombre de pixels de chaque couleur qui la compose dans chaque direction. Nous avons continué les travaux de la période précédente sur la reconstitution de matrices. Puis, travaillant simultanément sur les graphes et la tomographie discrète, nous avons naturellement tenté de relier les deux dans une approche originale. Il s'agit de trouver des colorations des arêtes ou sommets d'un graphe respectant des contraintes spécifiques, par exemple sur le nombre d'occurrences des couleurs le long de certains chemins du graphe. Cela nous a permis de mettre en évidence des connexions avec des problèmes d'ordonnancement, d'emploi du temps ou de planification. Nous avons également abordé la résolution de problèmes de tomographie discrète par la programmation mathématique (thèse en cours).

  Conception de réseaux robustes. Nous avons étudié les graphes hypotriangulés dans lesquels la suppression d'une arête n'augmente pas la distance entre deux sommets autres que les extrémités de l'arête ôtée. Nous avons obtenu des résultats concernant diverses propriétés de ces graphes, une caractérisation des hypotriangulés minimaux, la « complétion » d'un graphe pour qu'il devienne hypotriangulé. L'émergence des réseaux sans fil nous a incité à nous intéresser aux problèmes de chemins et d'arbres induits par les sommets sélectionnés. Nous avons commencé à étudier les problèmes de chemins induits entre une paire de sommets donnés dans un graphe pondéré. Ensuite nous avons conçu un algorithme polynomial pour la recherche d'un arbre induit couvrant quatre sommets donnés dans un graphe sans triangle.

  Allocation de registres et optimisation. Une collaboration entre les équipes OC et CPR a été initiée autour du thème de l'allocation de registres dans la compilation de programmes. La thèse de Doctorat de Benoît Robillard, soutenue en novembre 2010 et co-encadrée par un chercheur de chaque équipe, portait sur la vérification formelle et l'optimisation de l'allocation de registres. L'objectif de cette thèse était double : vérifier formellement, notamment à l'aide de l'assistant de preuves Coq, des algorithmes connus d'allocation de registres par coloration de graphes et, d'autre part, définir de nouveaux algorithmes optimisants pour cette étape de compilation.