CMAP
Rechercher
Accueil du site > Equipes_Fr_En_It > MAXPLUS > MAXPLUS
MAXPLUS
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 :
Wallis Filippi
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.
