Sites Inria

Version française

MAXPLUS Research team

Max-plus algebras and mathematics of decision

  • Leader : Stephane Gaubert
  • Research center(s) : CRI Saclay - Île-de-France
  • Field : Applied Mathematics, Computation and Simulation
  • Theme : Optimization and control of dynamic systems
  • Partner(s) : CNRS,Ecole Polytechnique
  • Collaborator(s) : Centre de Mathématiques Appliquées (CMAP) (UMR7641)

Team presentation

The MAXPLUS project-team develops theory, algorithms, and applications of algebras of max-plus type, in relation with the fields where these algebra arise: decision theory (deterministic and stochastic optimal control, game theory) asymptotic analysis and probability theory, modelling and performance analysis of discrete event dynamic systems (transportation or telecommunication networks, manufacturing systems), and operations research.

Research themes

  • Optimal control and game theory We are interested in dynamic decison problems, and particularly in dynamic programming methods, for which we develop theory (studying structure properties) and algorithms. We develop, or consider, in particular:
    • Monotone or nonexpansive dynamic systems, non-linear spectral theory.
    • Policy iteration algorithms, graph algorithms, large size problems in dynamic programming.
    • Hamilton-Jacobi-Bellman equations.
  • Discrete Event Systems. We are interested in analysis (performance evaluation) and control of dynamic discrete event systems, which arise in the modelling of transportation or telecommunication networks or in manufacturing systems. This includes:
    • Theory of max-plus linear systems (geometric approach).
    • Automata theory (automata with multiplicities).
    • Performance evaluation algorithms.
  • Operations research. One goal of the project is to develop max-plus algebraic tools for discrete optimization problems.
  • Max-plus algebra and related field. Max-plus algebra arises in several problems of mathematics and physics, in particular in asymptotic phenomena. We develop theoretical works in max-plus algebra, in relation with these problems. We study in particular:
    • Perturbations of eigenvalues
    • Idempotent probabilities and large deviations
    • Linear algebra and convexity
  • Software. Some of our works are implemented in the max-plus toolbox of Scilab.

International and industrial relations

  • STIC INRIA/Universités Tunisiennes collaboration with LAMSIN (ENIT).
  • Former NSF-INRIA collaboration with Rutgers University.
  • Several current academic collaborations, with researchers from: Birmingham, Bucharest, Harvard, ISI (New Delhi), Nottingham, Warwick.
  • Contacts with CEA.

Keywords: Max-plus or tropical algebras Optimal control Dynamic programming Game theory Discrete event systems Networks Operations research