Rechercher

sur ce site


Accueil du site > Equipes_Fr_En_It > MAXPLUS

TROPICAL

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

Équipe commune avec le Centre de Recherche Inria Saclay - Île-de-France

Voir aussi la page web de l’équipe-projet Inria MAXPLUS

Membres de l’équipe

Responsable :
- Stéphane Gaubert, Directeur de Recherche Inria

Responsable Permanente :
- Marianne Akian, Directeur de Recherche Inria

Assitante administrative des équipes Inria :
- Jessica Gameiro

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)

Chercheurs invités en 2012 :
- Srinivas Sridharan de l’Université de San Diego (USA), 5 jours
- Ngoc Tran de l’université de Berkeley, 3 jours
- Ricardo Kartz, du Conicet, Rosario (Argentine), 1 mois

Chercheurs invités en 2011 :
- William McEneaney, de l’Université de San Diego (USA), 4 jours
- Rajendra Bhatia, de l’Indian Statistical Institute, New Delhi (Inde), 1 semaine
- Thirukkannamangai Raghavan, de l’Université de l’Illinois de Chicago (USA), 2 jours
- Alexander Guterman, de l’Université d’état de Moscou, 5 jours
- Ricardo Kartz, du Conicet, Rosario (Argentine), 1 mois

Chercheurs invités en 2010 :
- Vladimir Gurvich, de l’Université Rutgers de Piscataway(USA), 1 semaine
- Alexander Guterman, de l’Université d’état de Moscou, 1 semaine
- Sergey Sergeev, de l’Université de Birmingham (UK), 1 semaine

Chercheurs invités en 2009 :
- Sergey Sergeev, de l’Université de Birmingham (UK), 1 semaine
- Vladimir Gurvich, de l’Université Rutgers de Piscataway(USA), 2 mois répartis dans l’année
- Bas Lemmens, de l’Université de Warwick(UK), 2 jours
- Francisco Valverde Albacete, de l’Université Carlos III de Madrid(Espagne), 1 semaine
- Carmen Pelaez Moreno, de l’Université Carlos III de Madrid(Espagne), 1 semaine
- William McEneaney, de l’Université de San Diego (USA), 2 jours

Chercheurs invités en 2008 :
- Bas Lemmens, de l’Université de Warwick, 3 jours
- Alexander Guterman, de l’Université d’état de Moscou, 3 mois répartis dans l’année

Post-doctorant :
- Sepideh Mirrahimi

Doctorants
- Pascal Benchimol
- Jean-Baptiste Dumont
- Andreas Marchesini
- Zheng Qu

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.


CMAP UMR 7641 École Polytechnique CNRS, Route de Saclay, 91128 Palaiseau Cedex France, Tél: +33 1 69 33 46 23 Fax: +33 1 69 33 46 46