En poursuivant votre navigation, vous acceptez l'utilisation de cookies destinés à améliorer la performance de ce site et à vous proposer des services et contenus personnalisés.

X

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

Équipe-projet commune avec l'Inria Saclay - Île-de-France

Responsable :

- Stéphane Gaubert, Directeur de Recherche Inria

Responsable Permanente :

- Marianne Akian, Directeur de Recherche Inria

Chercheurs confirmés :

- Jean-Pierre Quadrat, Directeur de Recherche Inria (à temps partiel dans MAXPLUS)
- Cormac Walsh, Chargé de Recherche Inria
- Xavier Allamigeon, Ingénieur de recherche

Personnel imaginaire

- Max Plus (nom collectif sous lequel des chercheurs de l’équipe ont publié des articles)

Assitante administrative des équipes Inria :

- Jessica Gameiro

 


Activités de recherche :

Le projet MAXPLUS développe la théorie, l’algorithmique, et les applications des algèbres de type max-plus ou tropicale, en relation avec les domaines où celles-ci interviennent : théorie de la décision (commande optimale déterministe et stochastique et 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 plus généralement, recherche opérationnelle. On peut distinguer les axes de recherche suivants.

Commande optimale et théorie des jeux

On s’intéresse aux problèmes de décision dans le temps. Nous étudions les propriétés théoriques des équations de la programmation dynamique et nous développons des algorithmes pour les résoudre. Les opérateurs de la programmation dynamique à temps discret peuvent être vus comme des cas particuliers de systèmes dynamiques monotones ou contractants, ou d’opérateurs de Perron-Frobenius non-linéaires. Nous étudions les points fixes (qui donnent la valeur de problèmes de décision en horizon infini), les vecteurs propres non linéaires (qui apparaissent dans les problèmes de décision avec critère ergodique), et le comportement asymptotique des orbites de tels opérateurs. Nous étudions aussi les équations aux dérivées partielles d’Hamilton-Jacobi-Bellman, lesquelles sont des équations de la programmation dynamique à temps continu. Notre but est de développer de nouveaux algorithmes et méthodes de discrétisation, à partir des résultats max-plus et de leurs généralisations. On s’intéresse plus particulièrement aux problèmes de grande taille, qui nécessitent le développement d’algorithmes rapides (algorithmes de graphe) ou de nouvelles approximations.

Systèmes à événements discrets

On s’intéresse à l’analyse (évaluation de performance), à l’optimisation, 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 en productique. On développe des modèles basés sur les systèmes dynamiques max-plus linéaires et leurs généralisations (automates, systèmes monotones ou contractants), permettant de représenter des phénomènes de synchronisation ou de concurrence (partage de ressources). On s’intéresse en particulier : au calcul ou à la maximisation de certaines mesures de performances ; à la fabrication de contrôleurs (ou même de “feedbacks”) vérifiant certaines contraintes de sécurité ou de service.

Théorie des perturbations

On étudie les problèmes asymptotiques dont les équations limites ont une structure de type max-plus, tels les perturbations singulières de valeurs propres ou les grandes déviations. On s’intéresse en particulier aux problèmes singuliers pour lesquels les résultats analytiques ou les méthodes numériques ont besoin d’être améliorés.

Recherche opérationnelle

Le rôle de l’algèbre max-plus dans certains problèmes de recherche opérationnelle est maintenant bien connu (programmation dynamique, problèmes de chemins, d’affectation ou de transport, certains problèmes d’ordonnancement, problèmes avec des contraintes dijunctives). Notre but est de développer plus avant les méthodes algébriques en recherche opérationnelle.

Algèbre max-plus et domaines reliés

Le groupe Maxplus travaille depuis de nombreuses années sur l’algèbre max-plus de base : analogues max-plus des modules et des polyèdres convexes, des déterminants, des notions de rang, des systèmes d’équations linéaires, des vecteurs propres, des équations polynomiales, mesures idempotentes, etc., qui ont souvent joué un rôle décisif dans nos applications précédentes de l’approche max-plus. L’intérêt pour certains problèmes de base max-plus est récemment apparu dans plusieurs autres domaines des mathématiques. Un de nos objectifs est de poursuivre l’étude de problèmes de base max-plus.

Logiciel

La boîte à outils max-plus de Scilab implémente le calcul de base max-plus ainsi que quelques algorithmes rapides de résolution de problèmes particuliers. On s’intéresse à développer de tels outils.

 

La page INRIA de l'équipe.