Sites Inria

English version

Equipe de recherche MAXPLUS

algèbres max-plus et mathématiques de la décision

  • Responsable : Stéphane Gaubert
  • Centre(s) de recherche : CRI Saclay - Île-de-France
  • Domaine : Mathématiques appliquées, calcul et simulation
  • Thème : Optimisation et contrôle de systèmes dynamiques
  • Partenaire(s) : CNRS,Ecole Polytechnique
  • Collaborateur(s) : CNRS, EC. POLYTECHNIQUE

Présentation de l'équipe

L'équipe-projet MAXPLUS développe la théorie, l'algorithmique, et les applications des algèbres de type max-plus, en relation avec les domaines où celles-ci interviennent: théorie de la décision (commande optimale déterministe et stochastique, théorie des jeux), analyse asymptotique et théorie des probabilités, modélisation et évaluation de performance de systèmes à évènements discrets(réseaux de transport ou de télécom, systèmes de production), et recherche opérationnelle.

Axes de recherche

  • Commande optimale et théorie des jeux. On s'intéresse aux problèmes de décision, et en particulier aux méthodes de programmation dynamique, que l'on aborde aussi bien du point vue théorique (étude des propriétés de structure), que de la résolution pratique (par le développement d'algorithmes rapides). On développe en particulier les thèmes suivants:
    • Systèmes dynamiques monotones ou contractants, théorie spectrale non-linéaire.
    • Algorithmes d'itération sur les politiques, algorithmes de graphe, problèmes de grande taille en programmation dynamique.
    • Étude et discrétisation d'équations d'Hamilton-Jacobi-Bellman.
  • Systèmes à événements discrets. On s'intéresse à l'analyse (évaluation de performance), et à la commande, de systèmes dynamiques à événements discrets, qui apparaissent dans la modélisation de réseaux (routiers, ferroviaires, télécom) et de systèmes de production. On développe en particulier les thèmes suivants:
    • Théorie des systèmes max-plus linéaires (approche géométrique).
    • Théorie des automates (automates à multiplicité).
    • Algorithmique pour l´evaluation de performance.
  • Recherche opérationnelle. On s'intéresse à l'application d'outils de type algèbre max-plus à la résolution de problèmes d'optimisation discrète.
  • Algèbre max-plus et domaines reliés. L'algèbre max-plus apparaît dans plusieurs problèmes des mathématiques et de la physique, en particulier dans l'étude de phénomènes asymptotiques. On s'intéresse au développement théorique de l'algèbre max-plus, en relation avec ces problèmes. On étudie notamment des questions de:
    • Perturbations de valeurs propres
    • Probabilités idempotentes et grandes déviations
    • Algèbre linéaire et convexité.
  • Logiciel. On développe la boîte à outils max-plus de Scilab, qui implémente certains de nos travaux.

Relations industrielles et internationales

  • Collaboration STIC INRIA/Universités Tunisiennes avec le LAMSIN (ENIT).
  • Ancienne collaboration NSF-INRIA avec l'université de Rutgers.
  • Plusieurs autres collaborations académiques en cours, avec des chercheurs de: Birmingham, Bucarest, Harvard, ISI (New Delhi), Nottingham, Warwick.
  • Contacts avec le CEA.

Mots-clés : Algèbres max-plus ou tropicales Commande optimale Programmation dynamique Théorie des jeux Systèmes à évenements discrets Réseaux Recherche opérationnelle

Suivez Inria