Archive - Le GDR RO 2012-2020

Outre un Conseil Scientifique, entité délibérative, et un Comité de Direction, entité opérationnelle, le GDR R.O structure principalement son activité autour de trois pôles scientifiques et de groupes de travail (GT). Le texte ci-dessous rappelle ce que sont les contenus correspondant à ces entités.

Un GT se dote d’une gouvernance adaptée à ces besoins et d’un représentant ; la gouvernance d’un pôle du GDR est dès lors assurée par ses deux responsables et par les représentants des groupes de travail relevant de ce pôle.

Les Pôles : ils correspondent à un découpage de l’activité relevant de la R.O, cohérent en termes scientifique, et exhaustif au regard de l’existant sur le territoire national. Ils ont vocation à être pérenne pour toute la période correspondant à la labellisation du GDR par le CNRS, et se déclinent comme suit :

• Pôle 1 : Modèles et Méthodes de l’Optimisation Combinatoire et Programmation Mathématiques (MMOCPM).

• Pôle 2 : Problèmes Opérationnels : Ordonnancement, Planification, Transport (POOPT)

• Pôle 3 : Décision : Modélisation, Prévision, Evaluation (DMPE)

Leur rôle est de :

• Aider les groupes de travail à se construire, à se coordonner entre eux, et à se coordonner avec les autres GDR du CNRS;

• Formuler, auprès du Conseil Scientifique du GDR, les propositions de soutien à ces GT;

• Organiser des actions d’animation à l’échelle du pôle, en direction notamment des jeunes ;

• Mener une réflexion prospective sur les tendances et les thèmes innovants.

Les Groupes de Travail : un groupe de travail constitue un espace de travail ouvert, sorte de laboratoire hors murs, regroupant des chercheurs intéressés par une même thématique. Il est le creuset d’échanges scientifiques récurrents et de projet collaboratifs, et associe des chercheurs issus aussi bien du monde académique que de celui des entreprises. Un chercheur peut émarger à l’activité de plusieurs groupes de travail, qui eux même peuvent relever de plusieurs pôles du GDR R.O ou de plusieurs GDR du CNRS. La labellisation et le soutien d’un GT par le GDR R.O supposent :

• le caractère ouvert de ce groupe : tout chercheur intéressé doit pouvoir y participer ;
• que ce groupe atteigne une certaine masse critique que l’on peut estimer à au moins une quinzaine de permanents ;
• une activité récurrente du groupe, concrétisée par au moins deux réunions annuelles et la participation à l’organisation de projets ou d’évènements, le rendu d’un rapport d’activité annuel, et la mention des logos CNRS et GDR dans sa communication ; cette activité doit être en cohérence avec le schéma global d’organisation du GDR et avec celui du CNRS.

Un GT se dote d’une gouvernance adaptée à ces besoins et d’un représentant ; la gouvernance d’un pôle du GDR est dès lors assurée par ses deux responsables et par les représentants des groupes de travail relevant de ce pôle.

A terme, la structuration des listes de diffusion du GDR devrait permettre une communication directe entre le GDR et un groupe de travail spécifique, ainsi qu’entre deux groupes de travail.

La gouvernance du GDR RO est structurée selon deux niveaux, celui du Conseil Scientifique, entité délibérative, et celui du Comité de Direction, entité opérationnelle.

Pôle  : Modèles et Méthodes de l’Optimisation Combinatoire et Programmation Mathématiques (MMOCPM).

• Programmation Mathématique, Méthodes Polyédrales

• Heuristiques et Métaheuristiques

• Schémas d’Approximation

• Programmation Dynamique, Programmation Quadratique

• Optimisation On Line, Optimisation Collaborative

• Complexité, Robustesse, Performances

• Structures Discrètes

• Optimisation de réseaux : flots, multi-flots, localisation…

• Techniques de Décomposition, Intégration, Optimisation Multi-Niveaux

Tendances et Priorités Scientifiques

Aujourd’hui, l’Optimisation Combinatoire reste un champ de recherche très actif tant en France qu’au niveau international. Le nombre croissant des domaines d’application et le besoin toujours renouvelé de solutions efficaces induisent une course sans fin pour l’amélioration des algorithmes existants, la mise au point de nouvelles techniques et paradigmes et l’étude de nouveaux problèmes. Au-delà, le domaine doit faire face à plusieurs enjeux, tant théoriques qu’appliqués. Sont mis ici en évidence ici les pôles d’études qui semblent actuellement les plus importants et que le GDR RO cherchera à impulser (on pourra constater qu’ils sont, globalement, en adéquation avec la nomenclature générale présentée en section 1 dans le descriptif des mots clés de l’pôle et que certains de ces pôles se retrouvaient dans les projets soutenus par le GDR entre 2007 et 2012).

• Sur le plan méthodologique :

  • Extension de la notion de Complexité en tant qu’outil d’évaluation des algorithmes

Il s’agit là d’un champ très important car il concilie d’une part des enjeux pratiques et des enjeux théoriques en créant un cadre visant à l’étude, en prolongement de la théorie de la complexité, de la structure des problèmes combinatoires en fonction de leur difficulté intrinsèque. Différents paradigmes illustrent différents types de compromis entre complexité algorithmique (temps de calcul) et qualité des solutions. Plusieurs paradigmes nouveaux ont été développés ces dernières années, qui visent à rapprocher complexité théorique (plus mauvais cas) et performances/difficultés réelles : algorithmique modérément exponentielle, complexité paramétrique, complexité en moyenne. Ils doivent à présent être approfondis tant dans la collecte de résultats pour de nouveaux problèmes combinatoires que du point de vue de la formalisation (mesure de performance, réductions, complétude, classes de difficulté, …).

• • Formalisation et approfondissement des paradigmes intégrant la dynamicité

Il s’agit ici de prendre en compte les situations réelles impliquant une information dégradée, partielle, dynamique ou incertaine : cadres on-line ou dynamiques, algorithmes embarqués, algorithmes distribués, optimisation robuste, optimisation combinatoire probabiliste, etc. Ces situations, de plus en plus fréquentes du fait des avancées technologiques (systèmes embarqués, internet, communication mobiles…), induisent une rupture avec les approches statiques traditionnelles, et exigent des innovations au niveau formalisme (définition de mesures de performances, de classes de difficulté, de réductions …).

• • Optimisation sur données de très grandes tailles et des données implicites

Des applications telles que le parcours de robots, des web services… impliquent de ne travailler à chaque instant que sur une petite partie des données ou des données compressées, ce qui change radicalement la nature des problèmes combinatoires. Le besoin apparait alors de concevoir des schémas d’approximation ad hoc pour des problèmes en théorie simples (polynomiaux-temps), mais néanmoins inefficaces dans de tels contextes.

• • Formalisation et approfondissement des paradigmes collaboratifs et coopératifs. Cette question, qui tend à devenir centrale, compte tenu des mutations dans la structure des processus de décisions à l’intérieur de la sphère socio-économique, pose la question des liens entre l’optimisation combinatoire et la théorie des jeux ou la théorie du choix social.

  • Intégration, décomposition, généricité, flexibilité

Il s’agit ici de l’étude, tant formelle que pratique, de schémas algorithmiques génériques permettant de mettre au point très rapidement et de manière semi-automatisée des méthodes efficaces pour de nouveaux problèmes ou des méthodes très simples à mettre en œuvre en situation d’urgence. Cette problématique, rendue cruciale au niveau des entreprises par les coûts de développement et les délais imposés, inclut la recherche de schémas algorithmiques très flexibles permettant de prendre en compte l’interaction homme/machine, les dialogues entre machines ou la collaboration entre différentes méthodes. On y retrouve aussi la question de la conception de schémas de décomposition des problèmes et des solutions logicielles qui épousent la structure des processus décisionnels, et se prêtent donc à l’intégration en un seul processus algorithmique de niveaux décisionnels distincts. In fine, un défi majeur concernera alors l’unification, au moins partiellement, dans un même cadre formel, de ces différents paradigmes, via par exemple des réductions entre différents cadres qui permettraient de les comparer et de transférer des résultats de l’un à l’autre.

• • Approximation, heuristiques et métaheuristiques

Une scission s’est faite, au fil des années entre l’algorithmique à garantie de performances et les heuristiques, deux champs visant pourtant à résoudre de manière efficace des problèmes difficiles. Un enjeu important et très fructueux serait de nouer plus de liens entre ces domaines pour permettre d’une part des études structurelles et de difficulté liées aux heuristiques (réductions adaptées, classification des problèmes, résultats d’impossibilité, …) et d’autre part la mise en œuvre de méthodes à garanties de performance plus efficaces en situation réelle.

• • La gestion de l’hétérogénéité en Programmation Mathématiques.

L’expérience montre que, malgré les progrès considérables enregistrés chez les bibliothèques d’optimisation (CPLEX, XPRESS, SCIIP, …), celles-ci ont énormément de difficultés à traiter des problèmes (par exemple des problèmes d’ordonnancement) présentant des variables de types et sémantiques très distinctes, articulées entre elles par des contraintes logiques. Il y a là un défi majeur, dont le fondement est de nature conceptuelle, si on veut rendre ces outils aptes au traitement efficace de certains problèmes pratiques.

• Au niveau des champs d’application, l’évolution déjà en cours qui tend à élargir le champ d’application des méthodes d’Optimisation Combinatoire va se poursuivre. Au-delà des domaines d’application phare, qui resteront très importants avec notamment l’apparition de nouveaux challenges dus aux nouvelles technologies, les Modèles et Méthodes de l’Optimisation Combinatoire se projetteront sur de nouveaux domaines, intégrant de façon prononcée des problématiques sociétales nouvelles :

  • celles dérivées des préoccupations croissantes liées à l’environnement, la gestion de l’énergie et des ressources naturelles.

• • celles issues des sciences sociales : économie, management, assurances, marketing, ressources humaines, innovation et transfert technologique …

  • celles issues de la demande croissante en services à la personne : AAL, pilotage de réseaux de capteurs, guidage de robots, … ainsi qu’en sciences de la Vie et de la Santé : Bioinformatique, management des situations d’urgence (EOR, stratégies d’évacuation, intégration des réseaux de communication en situation d’urgence, gestion des risques, …

  • celles issues de la projection des modèles d’optimisation vers des niveaux décisionnels apanages jusque-là des seuls managers : décision financière, design stratégique de réseaux, tarification, localisation, urbanisation, gestion centralisée d’un aéroport, d’une centrale nucléaire, etc.

Stratégie

Le développement de l’Optimisation Combinatoire s’est fait à partir d’un premier noyau thématique, par élargissement de la surface couverte et par approfondissement et sophistication des domaines recouvrés. Cette tendance rapproche l’Optimisation Combinatoire d’autres disciplines parmi lesquelles les mathématiques, l’informatique théorique, le Génie Logiciel, le Big Data Analytics. Cet élargissement a concerné les méthodes, mais aussi des domaines applicatifs de plus en plus nombreux : ingénierie, biologie, sciences sociales, management, …, et même les paradigmes de programmation : dynamique, collaboratif, interactif. De toute évidence, cette tendance va se poursuivre, voire se renforcer. Elle pourrait être vue comme induisant une difficulté de positionnement, voire un flou thématique mais au contraire, d’un point de vue positif, c’est la marque d’une grande richesse et l’occasion de nouer des liens avec d’autres champs thématiques.

Dans cette perspective, l’pôle Modèles et Méthodes de l’Optimisation Combinatoire et de la Programmation Mathématique du GDR RO cherchera :

• à se rapprocher d’autres GDR (IM, MOA, MACS…) ;

• à interagir avec les autres pôles du GDR sur certains sujets potentiellement partagés (Jeux Algorithmiques, Techniques PLNE pour le Transport ou l’Ordonnancement, Heuristiques et Métaheuristiques…) ;

• à structurer de façon efficace les communautés concernées, et à faciliter les regroupements collaboratifs et la circulation de l’information ;

• à promouvoir l’Innovation.

Pour ce faire, il affirmera une structuration en groupes de travail, de façon à développer des actions communes avec ses partenaires potentiels autour de ces groupes de travail. Il cherchera aussi, en interaction avec les acteurs industriels et avec la ROADEF, à identifier de nouveaux champs d’applications. Au plan international enfin, il s’efforcera de dessiner la carte des collaborations existantes, déjà très riches et nombreuses, et de fonctionner à l’image d’une plateforme pour la mutualisation des partenariats, l’émergence de nouvelles collaborations et la mise en place de consortiums en vue d’intégrer programmes nationaux et internationaux.