Méthodes tropicales
É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:
Cormac Walsh, Chargé de Recherche Inria
Xavier Allamigeon, Chargé de recherche, en détachement du corps des Mines
Constantin Vernicos, Maître de conférence à l'Université de Montpellier, en délégation à Inria
Yang Qi, Starting research position
Ingénieur:
Benjamin Nguyen-Van-Yen
Post-doc:
Armando Gutierrez Collaguazo
Doctorants:
Mael Forcier
Marin Boyet
Omar Saadi
Shanqing Liu
Quentin Canu
Quentin Jacquet
Antoine Béreau
Nicolas Vandame
Assistante Administrative:
Hanadi Dib
Activités de recherche :
Le projet TROPICAL 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.