RESEARCH CENTRE

Inria Saclay Centre
at Institut Polytechnique de
Paris

2023
ACTIVITY REPORT

Project-Team

TROPICAL

Tropical methods: structures, algorithms
and interactions

IN COLLABORATION WITH: Centre de Mathématiques Appliquées (CMAP)

DOMAIN

Applied Mathematics, Computation and
Simulation

THEME

Optimization and control of dynamic
systems

1

2

3
3

3
3
4
5
5

5
5
5
6
6

6
6

6
6

7
7
7
7

8
8
8
8

Contents

Project-Team TROPICAL

1 Team members, visitors, external collaborators

2 Overall objectives

2.1 Scientific context

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Research program

3.1 Optimal control and zero-sum games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Non-linear Perron-Frobenius theory, nonexpansive mappings and metric geometry . . . .
3.3 Tropical algebra and convex geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Tropical methods applied to optimization, perturbation theory and matrix analysis . . . . .

4 Application domains

4.1 Discrete event systems (manufacturing systems, networks, emergency call centers) . . . . .
4.2 Optimal control and games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Operations Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Computing program and dynamical systems invariants . . . . . . . . . . . . . . . . . . . . .

5 Social and environmental responsibility

5.1 Impact of research results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Highlights of the year

6.1 Awards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 New software, platforms, open data

7.1 New software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 Coq-Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.2 EmergencyEval

8 New results

8.1 Optimal control and zero-sum games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.1 Tropical numerical methods for stochastic control problems . . . . . . . . . . . . . .
8.1.2 Highway hierarchies for Hamilton-Jacobi-Bellman (HJB) PDEs . . . . . . . . . . . . .
8.1.3 Relative Krasnoselskii-Mann iteration for irreducible stochastic mean-payoff games
and entropy games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
8.1.4 Escape Rate Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
8.2 Non-linear Perron-Frobenius theory, nonexpansive mappings and metric geometry . . . .
9
9
8.2.1 Volume in Funk geometries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2.2 Invariant Finsler metrics on symmetric spaces . . . . . . . . . . . . . . . . . . . . . . . 10
8.3 Tropical algebra and convex geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.3.1 Formalizing convex polyhedra in Coq . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.3.2 Linear algebra over systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
8.3.3 Ambitropical convexity and Shapley retracts . . . . . . . . . . . . . . . . . . . . . . . . 11
8.3.4 Tropical linear regression and applications . . . . . . . . . . . . . . . . . . . . . . . . . 11
8.3.5 Roots over the symmetrized tropical semiring and eigenvalues of tropical symmetric

matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.3.6 Tropical Systems of Polynomial Equations . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.3.7 Systems of sparse polynomial equations and convex polytopes . . . . . . . . . . . . . 12
8.4 Tropical methods applied to optimization, perturbation theory and matrix analysis . . . . . 13
8.4.1 Tropicalization of interior point methods and application to complexity . . . . . . . 13
8.4.2 Tropical Nash equilibria and complementarity problems . . . . . . . . . . . . . . . . 13
8.4.3 Signed Tropicalization of Polars and application to Matrix Cones . . . . . . . . . . . . 13
8.4.4 Bounds on roots of (multivariate) polynomial systems . . . . . . . . . . . . . . . . . . 14
8.5 Algebraic aspects of tensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

8.5.1 Algebraic complexity of low-rank approximations . . . . . . . . . . . . . . . . . . . . . 14
8.6 Tensor ranks and complexity theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.7.1 Performance evaluation of emergency call centers and emergency services
. . . . . 14
8.7.2 Optimal pricing of energy contracts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

9 Bilateral contracts and grants with industry

16
9.1 Bilateral contracts with industry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

10 Partnerships and cooperations

10.2 International research visitors

16
10.1 International initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.1.1 Participation in other International Programs . . . . . . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.2.1 Visits of international scientists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
10.2.2 Visits to international teams
10.3 National initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
10.3.1 ANR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
10.3.2 Programme Gaspard Monge pour l’optimisation, la recherche opérationnelle et leurs

interactions avec les sciences des données . . . . . . . . . . . . . . . . . . . . . . . . . 18
10.3.3 Joint INRIA & AP-HP Bernoulli lab project: “URGE” . . . . . . . . . . . . . . . . . . . . 18

11 Dissemination

18
11.1 Promoting scientific activities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
11.1.1 Scientific events: organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
11.1.2 Scientific events: selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
11.1.3 Journal
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
11.1.4 Invited talks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
11.1.5 Research administration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
11.2 Teaching - Supervision - Juries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
11.2.1 Teaching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
11.2.2 Supervision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
11.2.3 Juries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
11.2.4 Communications at conferences and seminars . . . . . . . . . . . . . . . . . . . . . . 22

12 Scientific production

23
12.1 Major publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
12.2 Publications of the year
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
12.3 Cited publications

Project TROPICAL

1

Project-Team TROPICAL

Creation of the Project-Team: 2018 July 01

Keywords

Computer sciences and digital sciences

A1.2.4. – QoS, performance evaluation

A2.3.3. – Real-time systems

A2.4. – Formal method for verification, reliability, certification

A6.2.5. – Numerical Linear Algebra

A6.2.6. – Optimization

A6.4.2. – Stochastic control

A6.4.6. – Optimal control

A7.2.4. – Mechanized Formalization of Mathematics

A8.1. – Discrete mathematics, combinatorics

A8.2.1. – Operations research

A8.3. – Geometry, Topology

A8.4. – Computer Algebra

A8.9. – Performance evaluation

A8.11. – Game Theory

A9.6. – Decision support

Other research topics and application domains

B4.3. – Renewable energy production

B4.4. – Energy delivery

B4.4.1. – Smart grids

B6.6. – Embedded systems

B8.4. – Security and personal assistance

B8.4.1. – Crisis management

2

Inria Annual Report 2023

1 Team members, visitors, external collaborators

Research Scientists

• Stephane Gaubert [Team leader, INRIA, Senior Researcher, HDR]

• Marianne Akian [INRIA, Senior Researcher, HDR]

• Xavier Allamigeon [INRIA, Researcher, Corps des Mines, under secondment]

• Matías Bender [INRIA, Researcher, from Feb 2023]

• Yang Qi [INRIA, Starting Research Position, until Oct 2023]

• Cormac Walsh [INRIA, Researcher]

PhD Students

• Amanda Bigel [INRIA]

• Antoine Béreau [ENS RENNES via Ecole polytechnique]

• Quentin Canu [ENS PARIS-SACLAY, until Aug 2023]

• Pascal Capetillo [INRIA, from Nov 2023]

• Jonathan Hornewall [ENPC, Marne-la-vallée, from Nov 2023]

• Quentin Jacquet [EDF, until Oct 2023]

• Shanqing Liu [INRIA, from Oct 2023]

• Shanqing Liu [ECOLE POLY PALAISEAU, until Sep 2023]

• Loic Marchesini [ECOLE POLY PALAISEAU, from Sep 2023]

• Nicolas Vandame [ECOLE POLY PALAISEAU]

Technical Staff

• Benjamin Nguyen-Van-Yen [INRIA, Engineer, from Nov 2023]

Interns and Apprentices

• Loic Marchesini [INRIA, Intern, from Apr 2023 until Sep 2023]

Administrative Assistant

• Hanadi Dib [INRIA]

Visiting Scientists

• Gleb Koshevoi [CEMI, Russian Academy of Sciences, until Jan 2023]

• Gregorio Maljovich [UFRJ, from Jun 2023 until Jul 2023]

• Luz Pascal [Queensland University of Technology, from May 2023 until Jun 2023, PhD student]

Project TROPICAL

3

2 Overall objectives

The project develops tropical methods motivated by applications arising in decision theory (deterministic
and stochastic optimal control, game theory, optimization and operations research), in the analysis or
control of classes of dynamical systems (including timed discrete event systems and positive systems),
in the verification of programs and systems, and in the development of numerical algorithms. Tropical
algebra tools are used in interaction with various methods, coming from convex analysis, Hamilton–Jacobi
partial differential equations, metric geometry, Perron-Frobenius and nonlinear fixed-point theories,
combinatorics or algorithmic complexity. The emphasis of the project is on mathematical modelling and
computational aspects.

The subtitle of the Tropical project, namely, “structures, algorithms, and interactions”, refers to
the spirit of our research, including a methodological component, computational aspects, and finally
interactions with other scientific fields or real world applications, in particular through mathematical
modelling.

2.1 Scientific context

Tropical algebra, geometry, and analysis have enjoyed spectacular development in recent years. Tropical
structures initially arose to solve problems in performance evaluation of discrete event systems [58],
combinatorial optimization [64], or automata theory [100]. They also arose in mathematical physics
and asymptotic analysis [91, 86]. More recently, these structures have appeared in several areas of pure
mathematics, in particular in the study of combinatorial aspects of algebraic geometry [79, 115, 105, 84],
in algebraic combinatorics [74], and in arithmetics [68]. Also, further applications of tropical methods
have appeared, including optimal control [92], program invariant computation [50] and timed systems
verification [90], and zero-sum games [1].

The term ‘tropical’ generally refers to algebraic structures in which the laws originate from optim-
ization processes. The prototypical tropical structure is the max-plus semifield, consisting of the real
numbers, equipped with the maximum, thought of as an additive law, and the addition, thought of as a
multiplicative law. Tropical objects appear as limits of classical objects along certain deformations (“log-
limits sets” of Bergman, “Maslov dequantization”, or “Viro deformation”). For this reason, the introduction
of tropical tools often yields new insights into old familiar problems, leading either to counterexamples or
to new methods and results; see for instance [115, 96]. In some applications, like optimal control, discrete
event systems, or static analysis of programs, tropical objects do not appear through a limit procedure,
but more directly as a modelling or computation/analysis tool; see for instance [111, 58, 82, 65].

Tropical methods are linked to the fields of positive systems and of metric geometry [98], [12].
Indeed, tropically linear maps are monotone (a.k.a. order-preserving). They are also nonexpansive in
certain natural metrics (sup-norm, Hopf oscillation, Hilbert’s projective metric, . . . ). In this way, tropical
dynamical systems appear to be special cases of nonexpansive, positive, or monotone dynamical systems,
which are studied as part of linear and non-linear Perron-Frobenius theory [88], [2]. Such dynamical
systems are of fundamental importance in the study of repeated games [95]. Monotonicity properties are
also essential in the understanding of the fixed points problems which determine program invariants by
abstract interpretation [69]. The latter problems are actually somehow similar to the ones arising in the
study of zero-sum games; see [6]. Moreover, positivity or monotonicity methods are useful in population
dynamics, either in a discrete space setting [112] or in a PDE setting [60]. In such cases, solving tropical
problems often leads to solutions or combinatorial insights on classical problems involving positivity
conditions (e.g., finding equilibria of dynamical systems with nonnegative coordinates, understanding the
qualitative and quantitative behavior of growth rates / Floquet eigenvalues [10], etc). Other applications
of Perron-Frobenius theory originate from quantum information and control [104, 109].

3 Research program

3.1 Optimal control and zero-sum games

The dynamic programming approach allows one to analyze one or two-player dynamic decision problems
by means of operators, or partial differential equations (Hamilton–Jacobi or Isaacs PDEs), describing the

4

Inria Annual Report 2023

time evolution of the value function, i.e., of the optimal reward of one player, thought of as a function of
the initial state and of the horizon. We work especially with problems having long or infinite horizon,
modelled by stopping problems, or ergodic problems in which one optimizes a mean payoff per time
unit. The determination of optimal strategies reduces to solving nonlinear fixed point equations, which
are obtained either directly from discrete models, or after a discretization of a PDE.

The geometry of solutions of optimal control and game problems Basic questions include, especially
for stationary or ergodic problems, the understanding of existence and uniqueness conditions for the
solutions of dynamic programming equations, for instance in terms of controllability or ergodicity
properties, and more generally the understanding of the structure of the full set of solutions of stationary
Hamilton–Jacobi PDEs and of the set of optimal strategies. These issues are already challenging in the
one-player deterministic case, which is an application of choice of tropical methods, since the Lax-Oleinik
semigroup, i.e., the evolution semigroup of the Hamilton-Jacobi PDE, is a linear operator in the tropical
sense. Recent progress in the deterministic case has been made by combining dynamical systems and
PDE techniques (weak KAM theory [71]), and also using metric geometry ideas (abstract boundaries can
be used to represent the sets of solutions [83], [4]). The two player case is challenging, owing to the lack
of compactness of the analogue of the Lax-Oleinik semigroup and to a richer geometry. The conditions
of solvability of ergodic problems for games (for instance, solvability of ergodic Isaacs PDEs), and the
representation of solutions are only understood in special cases, for instance in the finite state space case,
through tropical geometry and non-linear Perron-Frobenius methods [46], [48], [2].

Algorithmic aspects: from combinatorial algorithms to the attenuation of the curse of dimension-
ality Our general goal is to push the limits of solvable models by means of fast algorithms adapted to large
scale instances. Such instances arise from discrete problems, in which the state space may so large that
it is only accessible through local oracles (for instance, in some web ranking applications, the number
of states may be the number of web pages) [72]. They also arise from the discretization of PDEs, in
which the number of states grows exponentially with the number of degrees of freedom, according to the
“curse of dimensionality”. A first line of research is the development of new approximation methods for
the value function. So far, classical approximations by linear combinations have been used, as well as
approximation by suprema of linear or quadratic forms, which have been introduced in the setting of dual
dynamic programming and of the so called “max-plus basis methods” [73]. We believe that more concise
or more accurate approximations may be obtained by unifying these methods. Also, some max-plus
basis methods have been shown to attenuate the curse of dimensionality for very special problems (for
instance involving switching) [93, 76]. This suggests that the complexity of control or games problems
may be measured by more subtle quantities that the mere number of states, for instance, by some forms
of metric entropy (for example, certain large scale problems have a low complexity owing to the presence
of decomposition properties, “highway hierarchies”, etc.). A second line of of our research is the develop-
ment of combinatorial algorithms, to solve large scale zero-sum two-player problems with discrete state
space. This is related to current open problems in algorithmic game theory. In particular, the existence
of polynomial-time algorithms for games with ergodic payment is an open question. See e.g. [51] for a
polynomial time average complexity result derived by tropical methods. The two lines of research are
related, as the understanding of the geometry of solutions allows to develop better approximation or
combinatorial algorithms.

3.2 Non-linear Perron-Frobenius theory, nonexpansive mappings and metric geo-

metry

Several applications (including population dynamics [10] and discrete event systems [58, 67, 53]) lead to
studying classes of dynamical systems with remarkable properties: preserving a cone, preserving an order,
or being nonexpansive in a metric. These can be studied by techniques of non-linear Perron-Frobenius
theory [2] or metric geometry [11]. Basic issues concern the existence and computation of the “escape
rate” (which determines the throughput, the growth rate of the population), the characterizations of
stationary regimes (non-linear fixed points), or the study of the dynamical properties (convergence to
periodic orbits). Nonexpansive mappings also play a key role in the “operator approach” to zero-sum
games, since the one-day operators of games are nonexpansive in several metrics, see [8].

Project TROPICAL

5

3.3 Tropical algebra and convex geometry

The different applications mentioned in the other sections lead us to develop some basic research
on tropical algebraic structures and in convex and discrete geometry, looking at objects or problems
with a “piecewise-linear ” structure. These include the geometry and algorithmics of tropical convex
sets [56],[1], tropical semialgebraic sets [36], the study of semi-modules (analogues of vector spaces when
the base field is replaced by a semi-field), the study of systems of equations linear in the tropical sense,
investigating for instance the analogues of the notions of rank, the analogue of the eigenproblems [49],
and more generally of systems of tropical polynomial equations. Our research also builds on, and concern,
classical convex and discrete geometry methods.

3.4 Tropical methods applied to optimization, perturbation theory and matrix ana-

lysis

Tropical algebraic objects appear as a deformation of classical objects thought various asymptotic pro-
cedures. A familiar example is the rule of asymptotic calculus,

−a/ϵ + e

−b/ϵ ≍ e

e

− min(a,b)/ϵ

,

−a/ϵ × e

−b/ϵ = e

e

−(a+b)/ϵ

,

(1)

+

when ϵ → 0
. Deformations of this kind have been studied in different contexts: large deviations, zero-
temperature limits, Maslov’s “dequantization method” [91], non-archimedean valuations, log-limit sets
and Viro’s patchworking method [115], etc.

This entails a relation between classical algorithmic problems and tropical algorithmic problems, one
may first solve the ϵ = 0 case (non-archimedean problem), which is sometimes easier, and then use the
information gotten in this way to solve the ϵ = 1 (archimedean) case.

In particular, tropicalization establishes a connection between polynomial systems and piecewise
affine systems that are somehow similar to the ones arising in game problems. It allows one to transfer
results from the world of combinatorics to “classical” equations solving. We investigate the consequences
of this correspondence on complexity and numerical issues. For instance, combinatorial problems can
be solved in a robust way. Hence, situations in which the tropicalization is faithful lead to improved
algorithms for classical problems. In particular, scalings for the polynomial eigenproblems based on
tropical preprocessings have started to be used in matrix analysis [77, 81].

Moreover, the tropical approach has been recently applied to construct examples of linear programs
in which the central path has an unexpectedly high total curvature [52],[7], and it has also led to positive
polynomial-time average case results concerning the complexity of mean payoff games. Similarly, we
are studying semidefinite programming over non-archimedean fields [36], [55], with the goal to better
understand complexity issues in classical semidefinite and semi-algebraic programming.

4 Application domains

4.1 Discrete event systems (manufacturing systems, networks, emergency call cen-

ters)

One important class of applications of max-plus algebra comes from discrete event dynamical sys-
tems [58]. In particular, modelling timed systems subject to synchronization and concurrency phenom-
ena leads to studying dynamical systems that are non-smooth, but which have remarkable structural
properties (nonexpansiveness in certain metrics , monotonicity) or combinatorial properties. Algebraic
methods allow one to obtain analytical expressions for performance measures (throughput, waiting time,
etc). A recent application, to emergency call centers, can be found in [53].

4.2 Optimal control and games

Optimal control and game theory have numerous well established applications fields: mathematical
economy and finance, stock optimization, optimization of networks, decision making, etc. In most of
these applications, one needs either to derive analytical or qualitative properties of solutions, or design
exact or approximation algorithms adapted to large scale problems.

6

Inria Annual Report 2023

4.3 Operations Research

We develop, or have developed, several aspects of operations research, including the application of
stochastic control to optimal pricing, optimal measurement in networks [106]. Applications of tropical
methods arise in particular from discrete optimization [65], [66], scheduling problems with and-or
constraints [97], or product mix auctions [114].

4.4 Computing program and dynamical systems invariants

A number of programs and systems verification questions, in which safety considerations are involved,
reduce to computing invariant subsets of dynamical systems. This approach appears in various guises in
computer science, for instance in static analysis of program by abstract interpretation, along the lines of
P. and R. Cousot [69], but also in control (eg, computing safety regions by solving Isaacs PDEs). These
invariant sets are often sought in some tractable effective class: ellipsoids, polyhedra, parametric classes
of polyhedra with a controlled complexity (the so called “templates” introduced by Sankaranarayanan,
Sipma and Manna [108]), shadows of sets represented by linear matrix inequalities, disjunctive constraints
represented by tropical polyhedra [50], etc. The computation of invariants boils down to solving large
scale fixed point problems. The latter are of the same nature as the ones encountered in the theory
of zero-sum games, and so, the techniques developed in the previous research directions (especially
methods of monotonicity, nonexpansiveness, discretization of PDEs, etc) apply to the present setting,
see e.g. [75, 78] for the application of policy iteration type algorithms, or for the application for fixed
point problems over the space of quadratic forms [6]. The problem of computation of invariants is indeed
a key issue needing the methods of several fields: convex and nonconvex programming, semidefinite
programming and symbolic computation (to handle semialgebraic invariants), nonlinear fixed point
theory, approximation theory, tropical methods (to handle disjunctions), and formal proof (to certify
numerical invariants or inequalities).

5 Social and environmental responsibility

5.1 Impact of research results

The team has developed collaborations on the dimensioning of emergency call centers, with Préfecture
de Police (Plate Forme d’Appels d’Urgence - PFAU - 17-18-112, operated jointly by Brigade de sapeurs
pompiers de Paris and by Direction de la sécurité de proximité de l’agglomération parisienne) and also
with the Emergency medical services of Assistance Publique – Hôpitaux de Paris (Centre 15 of SAMU75,
92, 93 and 94). This work is described further in Section 8.7.1. A recent extension of this work deals with
the modelling of medical emergency services, with the project “URGE” which started at the fall 2022, in
the framework of the joint INRIA & AP-HP “Bernoulli” lab.

6 Highlights of the year

6.1 Awards

• Stéphane Gaubert obtained the Michel Monpetit – INRIA Prize of Académie des Sciences, 2023.

• Marin Boyet (former PhD of the team) has obtained the PhD prize in Mathematics of Institut

polytechnique de Paris, for his work on emergency call centers [63].

• Antoine Béreau obtained the “Distinguished Student Author Award”, sponsored by SIGSAM and
Maplesoft, at the conference ISSAC (International Symposium on Symbolic and Algebraic Compu-
tation), Tromsø, Norway, July 2023.

Project TROPICAL

7

7 New software, platforms, open data

7.1 New software

7.1.1 Coq-Polyhedra

Name: Coq-Polyhedra

Keywords: Coq, Polyhedra, Automated theorem proving, Linear optimization

Scientific Description: Coq-Polyhedra is a library providing a formalization of convex polyhedra in the
Coq proof assistant. While still in active development, it provides an implementation of the simplex
method, and already handles the basic properties of polyhedra such as emptiness, boundedness,
membership. Several fundamental results in the theory of convex polyhedra, such as Farkas Lemma,
duality theorem of linear programming, and Minkowski Theorem, are also formally proved.

The formalization is based on the Mathematical Components library, and makes an extensive use
of the boolean reflection methodology.

Functional Description: Coq-Polyhedra is a library which aims at formalizing convex polyhedra in Coq

URL: https://github.com/nhojem/Coq-Polyhedra

Publications: hal-01673390, hal-03151656, hal-03915661, hal-01967575, hal-01967576

Contact: Xavier Allamigeon

Participants: Xavier Allamigeon, Vasileios Charisopoulos, Quentin Canu, Ricardo Katz, Pierre-Yves Strub

Partners: CIFASIS, Ecole Polytechnique

7.1.2 EmergencyEval

Keywords: Dynamic Analysis, Simulation, Ocaml, Emergency, Firefighters, Police

Scientific Description: This software aims at enabling the definition of a Petri network execution se-
mantic, as well as the instanciation and execution of said network using the aforedefined semantic.

The heart of the project dwells in its kernel which operates the step-by-step execution of the
network, obeying rules provided by an oracle. This user-defined and separated oracle computes
the information necessary to the kernel for building the next state using the current state. The base
of our software is the framework for the instanciation and execution of Petri nets, without making
assumptions regarding the semantic.

In the context of the study of the dynamics of emergency call centers, a second part of this software
is the definition and implementation of the semantic of call centers modelized as Petri nets, and
more specifically timed prioritized Petri nets. A module interoperating with the kernel enables
to include all the operational specificities of call centers (urgency level, discriminating between
operators and callers ...) while guaranteeing the genericity of the kernal which embeds the Petri net
formalism as such.

Functional Description: In order to enable the quantitative study of the throughput of calls managed by
emergency center calls and the assesment of various organisationnal configurations considered by
the stakeholders (firefighters, police, medical emergency service of the 75, 92, 93 and 94 French
departments), this software modelizes their behaviours by resorting to extensions of the Petri net
formalism. Given a call transfer protocol in a call center, which corresponds to a topology and
an execution semantic of a Petri net, the software generates a set of entering calls in accord with
the empirically observed statistic ditributions (share of very urgent calls, conversation length),
then simulates its management by the operators with respect to the defined protocol. Transitional
regimes phenomenons (peak load, support) which are not yet handled by mathematical analysis
could therefore be studied. The ouput of the software is a log file which is an execution trace of the

8

Inria Annual Report 2023

simulation featuring extensive information in order to enable the analysis of the data for providing
simulation-based insights for decision makers.

The software relies on a Petri net simulation kernel designed to be as modular and adaptable
as possible, fit for simulating other Petri-net related phenomenons, even if their semantic differ
greatly.

Contact: Xavier Allamigeon

Participants: Xavier Allamigeon, Benjamin Nguyen-van-yen

8 New results

8.1 Optimal control and zero-sum games

8.1.1 Tropical numerical methods for stochastic control problems

Participants: Marianne Akian, Luz Pascal.

In [113], we were interested in the numerical solution of the dynamic programming equation of discrete
time stochastic control problems, and we developped and studied several algorithms combining the
tropical or the max-plus based numerical method of McEneaney [94, 92], the stochastic max-plus scheme
proposed by Zheng Qu [103], and the stochastic dual dynamic programming (SDDP) algorithm of Pereira
and Pinto [99]. In [37], we also show that in the case of the dynamic programming equation associated
to a partially observable Markov Decision Process (POMDP), it is similar to the so called point based
algorithms developped in [101, 87, 110], which includes in particular SARSOP algorithm.

In an ongoing work, we are studying the convergence of SARSOP algorithm using the same techniques

as in [42].

8.1.2 Highway hierarchies for Hamilton-Jacobi-Bellman (HJB) PDEs

Participants: Marianne Akian, Stéphane Gaubert, Shanqing Liu, Yang Qi.

Hamilton-Jacobi-Bellman equations arise as the dynamic programming equations of deterministic or
stochastic optimal control problems. They allow to obtain the global optimum of these problems and to
synthetize an optimal feedback control, leading to a solution robust against system perturbations. Several
methods have been proposed in the litterature to bypass the obstruction of curse of dimensionality of
such equations, assuming a certain structure of the problem, and/or using “unstructured discretizations”,
that are not based on given grids. Among them, one may cite tropical numerical method, and probabilistic
numerical method. On another direction, “highway hierarchies”, developped by Sanders, Schultes and
coworkers [70, 107], initially for applications to on-board GPS systems, are a computational method that
allows one to accelerate Dijkstra algorithm for discrete time and state shortest path problems.

The aim of the PhD thesis of Shanqing Liu[89] was to develop new numerical methods to solve

Hamilton-Jacobi-Bellman equations that are less sensitive to curse of dimensionality.

In [26], we have developped a multilevel fast-marching method, extending to the PDE case the idea
of “highway hierarchies”. Given the problem of finding an optimal trajectory between two given points,
the method consists in refining the grid only in a neighborhood of the optimal trajectory, which is itself
computed using an approximation of the value function on a coarse grid.

In [18], we have considered general finite horizon deterministic optimal control problems, for which
we combine the idea of the multilevel grids around optimal trajectories with the max-plus finite element
method solving Hamilton-Jacobi equations introduced in [45].

More recently, we combined these ideas with an adaption of SDDP algorithm to semiconcave prob-

lems. We also apply our algorithm to numerically solve the N-body problem.

Project TROPICAL

9

8.1.3 Relative Krasnoselskii-Mann iteration for irreducible stochastic mean-payoff games and en-

tropy games

Participants: Marianne Akian, Stéphane Gaubert.

We studied in [19] an algorithm solving stochastic mean-payoff games, combining the ideas of
relative value iteration and of Krasnoselskii-Mann damping. We analysed its convergence and derived
parameterized complexity bounds for several classes of games satisfying irreducibility conditions. This is
a joint work with Ulysse Naepels and Basile Terver, two students at École polytechnique, IP Paris.

8.1.4 Escape Rate Games

Participants: Marianne Akian, Stéphane Gaubert, Loic Marchesini.

The aim of the PhD thesis of Loic Marchesini is to study a new class of repeated zero-sum games in
which the payoff of one player is the escape rate of a dynamical system whose dynamics depends on
the actions of both players. We begin with the case of dynamics obtained from nonexpansive operators.
Considering order preserving finite dimensional linear operators over the positive cone endowed with
Hilbert’s projective (semi-)metric, we recover the matrix multiplication games introduced by Asarin et
al. [57], which generalize the joint spectral radius of sets of nonnegative matrices. See also [47]. We
established a two-player analogue of “Mañe’s Lemma”, characterizing the value of the game.

8.2 Non-linear Perron-Frobenius theory, nonexpansive mappings and metric geo-

metry

8.2.1 Volume in Funk geometries

Participants: Cormac Walsh.

This is joint work with Dmitry Faifman (Tel Aviv) and Constantin Vernicos (Montpellier).
We are investigating the volume of metric balls in the Funk geometry [32]. This is an asymmetric
metric related to the Hilbert metric; indeed, the Hilbert metric is its symmetrisation. We are interested in
it because it is somewhat easier to work with than the Hilbert metric when dealing with volumes, and
exhibits similar interesting of behaviour. Given a convex body in Rn and a radius r , there is a unique
point x such that the Funk ball of radius r centered at x minimises the volume over all Funk balls of
the same radius. It is natural to conjecture that this minimum volume, which depends on the convex
body, it maximised when the body is a Euclidean ball. If this is true, one could recover Blaschke–Santaló
inequality by letting the radius tend to zero, and the centro-affine isoperimetric inequality by letting the
radius tend to infinity.

Similarly, one could conjecture that, under the assumption that the convex body is centrally sym-
metric, the minimum volume is minimised when the body is a Hanner polytope. Recall that these are
the polytopes that can be constructed from copies of the unit interval by taking products and polar
duals. This conjecture interpolates between the Mahler conjecture and Kalai’s flag conjecture. We can
prove it for unconditional bodies, that is, bodies that are symmetric through reflections in the coordinate
hyperplanes.

We have been studying in more detail the volume of balls in the Funk geometry when the convex
body is a polytope. Here, as in the case of the Hilbert metric, the volume grows polynomially with order
equal to the dimension, and the constant on front of the highest order term depends only on the number
of flags of the polytope. Thus, this term does not change when the polytope is perturbed in a way that
doesn’t change the combinatorics. This motivates us to look at the second highest order term. We have

10

Inria Annual Report 2023

developed the following formula for this in terms of the position of the vertices of the polytope and the
vertices of its dual.

′

Recall that polytopes have the following property: if F and F

, then there are exactly two faces G of dimension i such that F ⊂ G ⊂ F

are two faces of dimension i − 1 and
i + 1, respectively, and F ⊂ F
. So,
for each i ∈ {0, . . . , n − 1} and flag f , there is a unique flag, which we denote θi f , that differs from f only by
having a different face of dimension i . The group 〈θ0, . . . , θn−1〉 generated by these maps is known as the
monodromy group or connection group of the polytope P . To express the second term in the asymptotics
of the volume, we will need a particular element of this group, the complete flip θ := θn−1 ◦ · · · ◦ θ0. With
this notation, the second term is then αr n−1, where

′

′

α =

n
(n!)2

(cid:88)

f ∈Flags(P )

(cid:179)

1 −

(cid:68)
(θ f )n−1, f0

(cid:69)(cid:180)

.

log

Here, we are identifying the facet (θ f )n−1 with the associated vertex of the dual polytope.

Thus we get a new centro-affine invariant for polytopes. We have been studying this invariant: we can
show that in dimension 2 its only stationary points are the linear images of regular polygons centered at
the origin.

8.2.2 Invariant Finsler metrics on symmetric spaces

Participants: Cormac Walsh.

This is joint work with Bas Lemmens (Kent).
We are interested in metrics on symmetric spaces, in particular Finsler metrics that are invariant
under the symmetries of the space. In a previous paper [80], it was established that there is such a metric
natural associated to every representation of the symmetric space, which depends on the system of
weights of the representation. More precisely, one takes the convex hull of the weights and interprets that
as the dual ball in the Artin subspace. The lengths of all other vectors can then determined by invariance.
We are investigating this correspondence between representations and metrics in more detail. We wish to
answer the question, concretely, which known representations correspond to which invariant Finsler
metrics?

8.3 Tropical algebra and convex geometry

8.3.1 Formalizing convex polyhedra in Coq

Participants:

Xavier Allamigeon, Quentin Canu.

In a joint work with Pierre-Yves Strub (Meta), we have achieved the formal verification of a counter-
example of Santos et al. to the so-called Hirsch Conjecture on the diameter of polytopes. In contrast with
the pen-and-paper proof, our approach is entirely computational: we implement in Coq and prove cor-
rect an algorithm that explicitly computes, within the proof assistant, vertex-edge graphs of polytopes as
well as their diameter. The originality of this certificate-based algorithm is to achieve a tradeoff between
simplicity and efficiency. Simplicity is crucial in obtaining the proof of correctness of the algorithm.
This proof splits into the correctness of an abstract algorithm stated over proof-oriented data types and
the correspondence with a low-level implementation over computation-oriented data types. A special
effort has been made to reduce the algorithm to a small sequence of elementary operations (e.g., matrix
multiplications, basic routines on sets and graphs), in order to make the derivation of the correctness
of the low-level implementation more transparent. Efficiency allows us to scale up to polytopes with
a challenging combinatorics. For instance, we formally check the two counterexamples of Matschke,
Santos and Weibel to the Hirsch conjecture, respectively 20- and 23-dimensional polytopes with 36 425
and 73 224 vertices involving rational coefficients with up to 40 digits in their numerator and denominator.

Project TROPICAL

11

We also illustrate the performance of the method by computing the list of vertices or the diameter of
well-known classes of polytopes, such as (polars of) cyclic polytopes involved in McMullen’s Upper Bound
Theorem. This work has appeared in the proceedings of the conference CPP’23 [20].

Dealing with polyhedra and their faces raises the problem of formalizing order structures. We study
this problem in a joint work [29] with Cyril Cohen (Inria), Kazuhiko Sakaguchi (Inria) and Pierre-Yves
Strub (Meta). More precisely, using order structures in a proof assistant naturally raises the problem of
working with multiple instances of a same structure over a common type of elements. This goes against
the main design pattern of hierarchies used for instance in Coq’s MathComp or Lean’s mathlib libraries,
where types are canonically associated to at most one instance and instances share a common overloaded
syntax. We introduce new design patterns to leverage these issues, and apply them to the formalization
of order structures in the MathComp library. A common idea in these patterns is underloading, i.e.,
a disambiguation of operators on a common type. In addition, our design patterns include a way to
deal with duality in order structures in a convenient way. We hence formalize a large hierarchy which
includes partial orders, semilattices, lattices as well as many variants. We finally pay a special attention
to order substructures. We introduce a new kind of structure called prelattice. They are abstractions of
semilattices, and allow us to deal with finite lattices and their sublattices within a common signature.
As an application, we report on significant simplifications of the formalization of the face lattices of
polyhedra in the Coq-Polyhedra library.

8.3.2 Linear algebra over systems

Participants: Marianne Akian, Stéphane Gaubert.

In a joint work with Louis Rowen (Univ. Bar Ilan), [13], we study the properties of “systems”. The latter
provide a general setting encompassing extensions of the tropical semifields and hyperfields. Moreover,
they have the advantage to be well adapted to the study of linear or polynomial equations. In particular,
in [13], we characterize the semiring systems which arise from hyperrings.

In [24], we are studying linear algebra properties over a generalization of “systems” called “T-pairs”.

8.3.3 Ambitropical convexity and Shapley retracts

Participants: Marianne Akian, Stéphane Gaubert.

Closed tropical convex cones are the most basic examples of modules over the tropical semifield. They
coincide with sub-fixed-point sets of Shapley operators – dynamic programming operators of zero-sum
games. We study a larger class of cones, which we call “ambitropical” as it includes both tropical cones and
their duals. Ambitropical cones can be defined as lattices in the order induced by Rn. Closed ambitropical
cones are precisely the fixedpoint sets of Shapley operators. They are characterized by a property of best
co-approximation arising from the theory of nonexpansive retracts of normed spaces. Finitely generated
ambitropical cones arise when considering Shapley operators of deterministic games with finite action
spaces. Moreover, finitely generated ambitropical cones are special polyhedral complexes whose cells are
alcoved poyhedra, and locally, they are in bijection with order preserving retracts of the Boolean cube.
We also showed that a cone is ambitropical if and only if it is hyperconvex. This is a joint work with Sara
Vannucci (Praha). See [27].

8.3.4 Tropical linear regression and applications

Participants: Marianne Akian, Stéphane Gaubert, Yang Qi, Omar Saadi.

12

Inria Annual Report 2023

In [14], we show that the problem consisting in computing a best approximation of a collection of points
by a tropical hyperplane is equivalent to solving a mean payoff game, and also, to compute the maximal
radius of an inscribed ball in a tropical polytope. We provide an application to a problem of auction
theory – measuring the distance to equilibrium. We also study a dual problem — computing the minimal
radius of a circumscribed ball to a tropical polytope – and apply it to the rank-one approximation of
tropical matrices and tensors.

8.3.5 Roots over the symmetrized tropical semiring and eigenvalues of tropical symmetric matrices

Participants: Marianne Akian, Stéphane Gaubert.

The tropical semifield can be thought of as the image of a field with a non-archimedean valuation. It
allows in this way to study the asymptotics of Puiseux series with complex coefficients. When dealing with
Puiseux series with real coefficients and with its associated order, it is convenient to use the symmetrized
tropical semiring introduced in [102] (see also [58]), and the signed valuation which associates to any
series its valuation together with its sign.

In a work [25] which started during the postdoc of Hanieh Tavakolipour (Amirkabir University of
Technology) in the team, we study the roots’s multiplicities and the factorization of polynomials over the
symmetrized tropical semiring. We then deduce a Descartes’ rule of sign over ordered valued fields. This
builds in particular on [59] (for multiplicities) and on [36].

In a work with Dariush Kiani and Hanieh Tavakolipour (Amirkabir University of Technology), we study
with these tools the asymptotics of eigenvalues and eigenvectors of symmetric positive definite matrices
over the field of Puiseux series.

8.3.6 Tropical Systems of Polynomial Equations

Participants: Marianne Akian, Antoine Bereau, Stéphane Gaubert.

The PhD thesis of Antoine Bereau deals with systems of polynomial equations over tropical semifields.
In [17, 23], we established a Nullstellenstatz for sparse tropical polynomial systems. We reduce a polyno-
mial system to a linearized system obtained by an appropriate truncation of the Macaulay matrix. Our
approach is inspired by a construction of Canny-Emiris (1993), refined by Sturmfels (1994). It leads to
an improved estimate of the truncation degree. We also establish a tropical positivstellensatz, allowing
one to decide the containment of tropical basic semialgebraic sets. This method leads to the solution of
systems of tropical linear equalities and inequalities, which reduces to mean payoff games.

8.3.7 Systems of sparse polynomial equations and convex polytopes

Participants: Matías Bender.

Solving systems of polynomial equations is an intrinsically hard problem. In applications, almost
all the systems that we encounter have certain structure, so it is central to take advantage of this to be
able to solve bigger inputs. Among the most common structures, we find sparsity: the polynomial are
defined by a few set of monomials. If all the polynomial share the same sparsity pattern we say that the
system is “unmixed”; otherwise, we call it “mixed”. Several strategies had been proposed to deal with
sparse polynomial systems, being the more efficients ones the ones to deal with unmixed systems. In
our recent paper [30] with Pierre-Jean Spaenlehauer (Inria Nancy), we characterise the conditions under
which the specialised strategies developed for unmixed systems can be applied to mixed systems. Our
analysis relies on the combinatorics of convex polytopes associated to the input polynomials and toric
geometry. Furthermore, we show that deciding whenever this can be done is a NP-hard problem.

Project TROPICAL

13

8.4 Tropical methods applied to optimization, perturbation theory and matrix ana-

lysis

8.4.1 Tropicalization of interior point methods and application to complexity

Participants:

Xavier Allamigeon, Stéphane Gaubert, Nicolas Vandame.

It is an open question to determine if the theory of self-concordant barriers can provide an interior
point method with strongly polynomial complexity in linear programming. In the special case of the
logarithmic barrier, it was shown in [52],[7] that the answer is negative.

In a subsequent work [43] with Abdellah Aznag (Columbia University) and Yassine Hamdi (Ecole
Polytechnique), we have studied the tropicalization of the central path associated with the entropic
barrier studied by Bubeck and Eldan (Proc. Mach. Learn. Research, 2015), i.e., the logarithmic limit of this
central path for a parametric family of linear programs defined over the field of Puiseux series. Our main
result is that the tropicalization of the entropic central path is a piecewise linear curve which coincides
with the tropicalization of the logarithmic central path studied by Allamigeon et al. in [52],[7].

In the work [40], we have now shown that none of the self-concordant barrier interior point methods
is strongly polynomial. This result is obtained by establishing that, on parametric families of convex
optimization problems, the log-limit of the central path degenerates to the same piecewise linear curve,
independently of the choice of the barrier function. We also provided an improved counter example,
with an explicit linear program that falls in the same class as the Klee–Minty counterexample, i.e., a
n-dimensional combinatorial cube, in which the number of iterations is 2n.

A key tool in this work consists of metric inequalities, controlling the convergence of the log-images
of semialgebraic sets to a polyhedral complex (their tropicalization). Explicit convergence bounds, valid
under certain genericity assumptions, have been subsequently established.

In a joint work [39] with Daniel Dadush, Georg Loho, Bento Natura and László Végh, we establish a
natural connection between the complexity of interior point methods and that of the simplex method,
and deduce combinatorial bounds on the number of iterations. In more details, we introduce a new
polynomial-time path-following interior point method where the number of iterations also admits a
combinatorial upper bound O(2nn1.5 log n) for an n-variable linear program in standard form. The
number of iterations of our algorithm is at most O(n1.5 log n) times the number of segments of any
piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number
of iterations of any path following interior point method up to this polynomial factor. The overall
exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the
number of pieces bounded by the total length of 2n shadow vertex simplex paths.

8.4.2 Tropical Nash equilibria and complementarity problems

Participants:

Xavier Allamigeon, Stéphane Gaubert.

Linear complementarity programming is a generalization of linear programming which encompasses
the computation of Nash equilibria for bimatrix games. While the latter problem is PPAD-complete,
we show in [44] that the analogue of this problem in tropical algebra can be solved in polynomial time.
Moreover, we prove that the Lemke–Howson algorithm carries over the tropical setting and performs a
linear number of pivots in the worst case. A consequence of this result is a new class of (classical) bimatrix
games for which Nash equilibria computation can be done in polynomial time. This is joint work with
Frédéric Meunier (Cermics, ENPC).

8.4.3 Signed Tropicalization of Polars and application to Matrix Cones

14

Inria Annual Report 2023

Participants: Marianne Akian, Xavier Allamigeon, Stéphane Gaubert.

With Sergey Sergeev (U. Birmingham), we study in [22] the tropical analogue of the notion of polar of a
cone over the symmetrized tropical semiring (see for instance [102, 58]). We characterize in particular the
tropical polars of sets of nonnegative tropical vectors, and relate them with images by the nonarchimedean
valuation of classical polars over real closed nonarchimedean fields. We study in particular cones of
matrices, and optimization problems.

8.4.4 Bounds on roots of (multivariate) polynomial systems

Participants: Marianne Akian, Stéphane Gaubert.

With Gregorio Malajovich (Univ. Federal Rio de Janeiro (UFRJ), we study the approximation of the
solutions of (classical) polynomial systems, using the roots of some associated tropical polynomial
systems, or more generally techniques of tropical geometry. In particular, in a work in progress, we
generalize the Cauchy and Lagrange bounds to multivariate polynomials.

8.5 Algebraic aspects of tensors

8.5.1 Algebraic complexity of low-rank approximations

Participants:

Yang Qi.

In a joint work with Khazhgali Kozhasov (Université Côte d’Azur), Alan Muniz (Universidade Estadual
de Campinas), and Luca Sodomaco (KTH Stockholm) [34], we study the algebraic complexity of Euclidean
distance minimization from a generic tensor to the set of rank-one tensors. More precisely, we study the
number of complex critical points of this optimization problem, which is called the Euclidean distance
(ED) degree of the Segre-Veronese variety in algebraic geometry. We view this invariant as a function
of inner products and show this function achieves its minimal value at Frobenius inner product for the
matrix case. In addition, we discuss the above optimization problem for other varieties as well.

8.6 Tensor ranks and complexity theory

Participants:

Yang Qi.

With Christian Ikenmeyer (Warwick), we study the complexity classes WR which is defined by sym-
metric rank and its Zariski closure VWR which is defined by symmetric border rank. In particular, we
show these two classes equal, i.e., for a given symmetric tensor T with symmetric border rank r , when r
is small, the symmetric rank of T is polynomially bounded by r .

8.7 Applications

8.7.1 Performance evaluation of emergency call centers and emergency services

Participants:

Xavier Allamigeon, Pascal Capetillo, Stéphane Gaubert, Ben-
jamin Nguyen-Van-Yen.

Project TROPICAL

15

Since 2014, we have been collaborating with Préfecture de Police (Régis Reboul and LcL Stéphane
Raclot), more specifically with Brigade de Sapeurs de Pompiers de Paris (BSPP) and Direction de Sécurité
de Proximité de l’agglomération parisienne (DSPAP), on the performance evaluation of the new organiza-
tion (PFAU, “Plate forme d’appels d’urgence”) to handle emergency calls to firemen and policemen in the
Paris area. We developed analytical models, based on Petri nets with priorities, and fluid limits, see [53],
[54], [61]. In 2019, with four students of École polytechnique, Céline Moucer, Julia Escribe, Skandère
Sahli and Alban Zammit, we performed case studies, showing the improvement brought by the two level
filtering procedure.

Moreover, in 2019, this work has been extended to encompass the handling of health emergency
calls, with a new collaboration, involving responsibles from the four services of medical emergency aid
of Assistance Publique – Hôpitaux de Paris (APHP), i.e., with SAMU75, 92, 93, 94, in the framework of
a project coordinated by Dr. Christophe Leroy from APHP. As part of his PhD work, Marin Boyet have
developed Petri net models capturing the characteristic of the centers (CRRA) handling emergency calls
the SAMU, in order to make dimensioning recommendations. Following this, we have been strongly
solicited by APHP during the pandemic of Covid-19 in order to determine crisis dimensioning of SAMU.
In parallel, we have further investigated the theoretical properties of timed Petri nets with preselection
and priority routing. We represent the behavior of these systems by piecewise affine dynamical systems.
We use tools from the theory of nonexpansive mappings to analyze these systems. We establish an
equivalence theorem between priority-free fluid timed Petri nets and semi-Markov decision processes,
from which we derive the convergence to a periodic regime and the polynomial-time computability of
the throughput. More generally, we develop an approach inspired by tropical geometry, characterizing
the congestion phases as the cells of a polyhedral complex. These results are illustrated by the application
to the performance evaluation of emergency call centers of SAMU in the Paris area. These results have
been published in [35].

In [38], we provided explicit formulæ allowing one to compute the time needed by a call center to
return to a stationary state after a bulk of calls. This is based on a turnpike-type theorem for Markov
decision processes.

These results are also presented in the Phd thesis [63].
In a followup work, in the framework of the URGE project (see Section 10.3.3 below) we are extending
these models in order to evaluate the dimensioning of emergency departments. This is the object of the
PhD work of Pascal Capetillo (which started in Nov. 2023).

8.7.2 Optimal pricing of energy contracts

Participants:

Stéphane Gaubert, Quentin Jacquet.

The PhD thesis of Quentin Jacquet [85] was cosupervised by Stéphane Gaubert, Clémence Alasseur
(EDF Labs), and Wim van Ackooij (EDF Labs). It concerns the application of bilevel programming methods
to the pricing of electricity contracts. We investigated in [16] a new model of customer’s response, based
on a quadratic regularization. We showed that this model has qualitative properties and a realism similar
to the classical models based on the logit-response, while being amenable to mathematical programming
and polyhedral techniques, and so to exact solutions, via a reduction to quadratic complementary
problems. An application to a set of instances representative of French electricity contracts was also
developed in [16].

In [41], we developed a model representing the response of a population of customers to dynamic
price offers. This lead to a mean-field Markov decision model, with ergodic cost. We showed in particular
the optimality of pricing policies characterized by periodic discounts.

The preprint [28] develops a mean field game model to model an incentive pricing scheme, in which

agents compete to get the best reward.

The conference article [21] develops a method to compute an optimal menu of contracts of a pre-
scribed cardinality, optimizing the income of a provider, taking into account the agent’s characteristics.

16

Inria Annual Report 2023

9 Bilateral contracts and grants with industry

9.1 Bilateral contracts with industry

Participants:

Stéphane Gaubert.

• Optimal pricing of energy and services. Collaboration of Stéphane Gaubert with Clémence Alasseur
and Wim Van Ackooij, from EDF Labs, with the Phd Work of Quentin Jacquet (CIFRE PhD, 2020-
2023), supervised by Stéphane Gaubert.

10 Partnerships and cooperations

10.1 International initiatives

10.1.1 Participation in other International Programs

Bilateral project FACCTS with the University of Chicago

Participants:

Stéphane Gaubert.

Title: Tropical geometry of deep learning

Partner Institution(s): University of Chicago (Statistics) and Ecole polytechnique.

Program: Bilateral project FACCTS, between the University of Chicago (Statistics) – Lek-Heng Lim– and

Ecole polytechnique – Stéphane Gaubert–

Partners: Lek-Heng Lim

Date/Duration: 2021-2023

10.2 International research visitors

10.2.1 Visits of international scientists

Other international visits to the team

Gleb Koshevoy

Status Senior Researcher.

Institution of origin: Institute of Information Transmission Problems (Kharkevich Institute), Russian

Academy of Sciences.

Country: Russia.

Dates: November 1, 2022 to January 31, 2023.

Context of the visit: INRIA Saclay invited professor programme. Gleb Koshevoy is invited to collaborate
with the Tropical team, on topics at the interface of algebraic combinatorics, discrete convexity and
tropical geometry. The collaboration program covers the study of ambitropical and hyperconvexity,
their interactions with F -polynomials, and tropical positivstellensatze.

Mobility program/type of mobility: research stay.

Project TROPICAL

Luz Pascal

Status PhD.

17

Institution of origin: Queensland University of Technology.

Country: Australia.

Dates: May 30, 2023 to June 20, 2023.

Context of the visit: Participation of Marianne Akian to the supervision of Luz Pascal on the algorithms
for Partially Observable Markov Decision Processes and their applications to adaptive management
of species.

Mobility program/type of mobility: research stay.

Gregorio Malajovich

Status Senior Researcher.

Institution of origin: Mathematical Institute, Universidade Federal do Rio de Janeiro.

Country: Brazil.

Dates: June 22, 2023 to July 7, 2023.

Context of the visit: Collaboration with the TROPICAL team (Marianne Akian and Stéphane Gaubert)

on tropical geometry applied to the localization of roots of polynomial systems.

Mobility program/type of mobility: research stay.

10.2.2 Visits to international teams

Research stays abroad

Matías Bender

Visited institution: University of Texas at San Antonio.

Country: US

Dates: October 30, 2023 to November 3, 2023.

Context of the visit: Collaboration with Alperen Ergür.

Mobility program/type of mobility: research stay.

10.3 National initiatives

10.3.1 ANR

Participants: Marianne Akian, Xavier Allamigeon, Cormac Walsh, Stéphane Gaubert.

• Project ANR HilbertXField (“Géométries de Hilbert sur tout corps valué”). ANR leader: Antonin
Guilloux. Partners: IMJ-PRG/OURAGAN (Sorbonne Université, pole leader Antonin Guilloux),
CMAP/TROPICAL (Inria, pole leader: Cormac Walsh), Institut Fourier (Grenoble, pole leader Anne
Parreau).

18

Inria Annual Report 2023

10.3.2 Programme Gaspard Monge pour l’optimisation, la recherche opérationnelle et leurs interac-

tions avec les sciences des données

Participants: Matías Bender.

• SOAP - Sparsity in Optimization via Algebra and Polynomials, with Elias Tsigaridas (IMJ), project

funded by FMJH within the PGMO programme.

10.3.3 Joint INRIA & AP-HP Bernoulli lab project: “URGE”

• The project URGE (Analyse des parcours patients aux URgences et optimisation des prises en
charGE), started at the fall 2022, in the framework of the joint INRIA & AP-HP Bernoulli lab. The
goal of the project is to develop modelling, simulation, performance analysis, and visualization
tools, in order to help physicians to optimize the staffing of emergency services. This collaborative
project, of four years, involves the Tropical and Aviz teams from INRIA Saclay, the Dyogene team
from INRIA Paris, and the Fédération Hospitalo-Universitaire (FHU) / IMPEC Improving Emergency
Care, AP-HP / Sorbonne Université / INSERM. The project is led by X. Allamigeon (Tropical) and
Y. Yordanov (AP-HP, Saint-Antoine) and involves S. Gaubert, B. Nguyen (Tropical), Ch. Fricker
(Dyogene), J.D. Fekete (Aviz).

11 Dissemination

11.1 Promoting scientific activities

11.1.1 Scientific events: organisation

General chair, scientific chair

• Stéphane Gaubert is the coordinator of the Gaspard Monge Program for Optimization, Operations
Research and their interactions with data sciences (PGMO), a corporate sponsorhip program,
operated by Fondation Mathématique Jacques Hadamard, supported by EDF, see Pgmo site.

Member of the organizing committees

• Stéphane Gaubert co-organizes the “Séminaire Parisien d’Optimisation” at Institut Henri Poincaré.

Organization of special sessions at conferences

• Marianne Akian, organization of minisymposium “Équations d’Hamilton-Jacobi-Bellman et de

jeux à champ moyen” at SMAI 2023, May 22-26, 2023, Le Gosier en Guadeloupe.

• Marianne Akian, organization of minisymposium “Computational Tropical Geometry” at SIAM

Conference on Applied Algebraic Geometry (AG23), Eindhoven, The Netherlands.

• Matìas Bender, organization of minisymposium “Efficient Symbolic and Numerical Algorithms for
Polynomial Systems” at SIAM Conference on Applied Algebraic Geometry (AG23), Eindhoven, The
Netherlands.

• Matìas Bender, organization of invited session “Nonlinear Algebra and its Application” at PGMO

Days 2023, Palaiseau, France.

• Yang Qi, organization of minisymposium “Geometry in optimization and numerical (multi)linear
algebra" at SIAM Conference on Applied Algebraic Geometry (AG23), Eindhoven, The Netherlands.

Project TROPICAL

19

11.1.2 Scientific events: selection

Chair of conference program committees

• Stéphane Gaubert, co-chair of the PGMO Days 2023, EDF Labs, 28-29 Nov.

Member of the conference program committees

• Marianne Akian, member of the Program Commitee of ISSAC’2023.

• Marianne Akian, member of the Scientific Commitee of 11th French Biennal of SMAI (SMAI 2023).

• Stéphane Gaubert, member of the scientific committee of the Mathematics and Decision Confer-

ence, 11 – 15 December 2023 Place: UM6P Ben Guerir, Morocco.

• Stéphane Gaubert, member of the scientific committee of the workshop Modélisation des Systèmes

Réactifs (MSR’23), Toulouse.

11.1.3 Journal

Member of the editorial boards

• Stéphane Gaubert: member of the editorial board of Journal of Dynamics and Games, Linear and

Multilinear Algebra, RAIRO, Springer-SMAI book series.

11.1.4 Invited talks

• Marianne Akian:

– Minisymposium “Manifestations of the Mixed Volume” at SIAM Conference on Applied
Algebraic Geometry (AG23), July 2023, Eindhoven, The Netherlands. Talk : “Cauchy and
Lagrange Bounds for Multivariate Polynomials” (work with Stéphane Gaubert and Gregorio
Malajovich).

– Minisymposium “Numerical methods for Hamilton-Jacobi equations and their applications”
at 10th International Congress on Industrial and Applied Mathematics (ICIAM 2023), August
2023, Tokyo, Japan. Talk: “Tropical and multi-level numerical methods for solving optimal
control problems” (work with Stéphane Gaubert and Shanqing Liu).

– Invited talk at Mathematics & Decision Conference, 11-15 December 2023, UM6P Ben Guerir,
Morocco. Title: “Repeated zero-sum games: from operators to algorithms and tropical
geometry”.

• Xavier Allamigeon

– Journée des lauréats des prix de l’Académie des Sciences, section “Mécanique et Informatique”,

Paris, France, mai 2023. Titre : A Formal Disproof of the Hirsch Conjecture.

– Exposé invité à la conférence “Highlights of Algorithms”, Prague, République Tchèque, juin

2023. Titre : No self-concordant barrier interior point method is strongly polynomial.

– Minisymposium “Computational Tropical Geometry” at SIAM Conference on Applied Algeb-
raic Geometry (AG23), July 2023, Eindhoven, The Netherlands. Talk: “Tropical Nash Equilibria
and Oriented Matroids” (work with Stéphane Gaubert and Frédéric Meunier).

– Exposé invité au 27ème séminaire “Polyèdres et Optimisation Combinatoire”, Paris, France,
décembre 2023. Titre : No self-concordant barrier interior point method is strongly polynomial.

• Matìas Bender

– Minisymposium “Manifestations of the Mixed Volume” at SIAM Conference on Applied
Algebraic Geometry (AG23), July 2023, Eindhoven, The Netherlands. Talk: “Dimension Results
for Polynomial Systems Over Complete Toric Varieties”.

20

Inria Annual Report 2023

– Minisymposium “Recent Advances on Polynomial System Solving” at 10th International
Congress on Industrial and Applied Mathematics (ICIAM 2023), August 2023, Tokyo, Japan.
Talk: “Dimension Results for Polynomial Systems Over Complete Toric Varieties”.

– Weekly seminar of the FCFS at Universidad Autónoma de Chiapas.

• Antoine Béreau:

– Minisymposium “Manifestations of the Mixed Volume” at SIAM Conference on Applied
Algebraic Geometry (AG23), July 2023, Eindhoven, The Netherlands. Talk: “The Tropical
Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems” (work with Marianne
Akian and Stéphane Gaubert).

• Stéphane Gaubert:

– 25th Conference of the International Linear Algebra Society, Madrid, June 2023 (Invited
Minisymposium). Talk: “Turing-model complexity estimates in geometric programming and
application to the computation of the spectral radius of nonnegative tensors.”.

– Jon-Shmuel Halfway to Twelfty celebration, ENPC, July 2023. Talk: “Ambitropical convexity,

injective hulls of metric spaces, and mean-payoff games.”

– Minisymposium “Computational Tropical Geometry” at SIAM Conference on Applied Algeb-
raic Geometry (AG23), July 2023, Eindhoven, The Netherlands. Talk: “Ambitropical Convexity,
Injective Hulls and Mean-Payoff Games” (work with Marianne Akian and Sara Vannucci).

– Minisymposium “Advances in Optimization” at 10th International Congress on Industrial and
Applied Mathematics (ICIAM 2023), August 2023, Tokyo, Japan. Talk: “Tropical convexity:
application to linear programming and mean-payoff games”.

– Combinatorics and Arithmetic for Physics, IHES, Nov. 2023. Talk: “The Nullstellensatz and
Positivstellensatz for Sparse Tropical Polynomial Systems, and Parametric Mean-Payoff Games”
(joint work with Marianne Akian and Antoine Béreau).

• Yang Qi:

– Optimization Seminar, Telecom Paris, April 2023, Talk: “Tropical linear regression and low-

rank approximation — a first step in tropical data analysis”.

– MC2 Seminar, ENS Lyon, May 2023, Talk: “Tropical linear regression and low-rank approxima-

tion — a first step in tropical data analysis”.

– Frontiers of computational mathematics, Kunming, China, August 2023, Talk: “Tropical data

analysis”.

• Nicolas Vandame:

– Minisymposium “Computational Tropical Geometry” at SIAM Conference on Applied Algeb-
raic Geometry (AG23), July 2023, Eindhoven, The Netherlands. Talk: “No Self-Concordant
Barrier Interior Point Method Is Strongly Polynomial” (work with Stéphane Gaubert and Xavier
Allamigeon).

• Cormac Walsh:

– “Workshop on Ordered Vector Spaces and Positive Operators”, Wuppertal, Germany, 29

March–1 April 2023. Talk: “Order and metric structures on cones”.

11.1.5 Research administration

Inria research administration

• Marianne Akian: Elected member of Inria’s Scientific Board.

• Matìas Bender: Member of the scientific committee of INRIA Saclay.

Project TROPICAL

21

Other research administration

• Marianne Akian: “Secrétaire Générale” of SMAI since July 2023.

11.2 Teaching - Supervision - Juries

11.2.1 Teaching

• Marianne Akian

– Course “Markov decision processes: dynamic programming and applications” joint between
(3rd year of) ENSTA and M2 “Mathématiques et Applications”, U. Paris Saclay, “Optimization”,
30 hours.

• Xavier Allamigeon

– Petites classes et encadrement d’enseignements d’approfondissement de Recherche Opéra-
tionnelle en troisième année à l’École Polytechnique (programme d’approfondissement de
Mathématiques Appliquées) (niveau M1).

– Cours “Theoretical Aspects of Linear Programming” du M2 “Optimisation” de l’Université

Paris Saclay.

– Co-responsabilité du programme d’approfondissement en mathématiques appliquées (troisième

année) à l’École Polytechnique (jusqu’à septembre 2023).

• Matìas Bender

– Exercises classes for the second year of Bachelor program of Ecole polytechnique in the

framework of a “Chargé d’ensegnement”.

– Course “Computational commutative algebra” at the CIMPA summer school Algebraic and

Tropical Methods for Solving Differential Equations, Oaxaca, Mexico.

• Antoine Béreau

– Exercises classes for the first year of Bachelor program of Ecole polytechnique in the frame-

work of a “Monitorat”.

• Amanda Bigel

– Exercises classes for the first year of Bachelor program of Ecole polytechnique in the frame-

work of a “Monitorat”.

• Stéphane Gaubert

– Co-head of the Master “Optimization” of University Paris-Saclay and IPP.

– Course “Systèmes à Événements Discrets”, option MAREVA, ENSMP.

– Course “Algèbre tropicale pour le contrôle optimal et les jeux” of “Contrôle, Optimisation et
Calcul des Variations” (COCV) of M2 “Mathématiques et Applications” of Sorbonne University
and École Polytechnique.

– Lecture of Operations Research, third year of École Polytechnique. The lectures notes were

published as a book [62].

• Shanqing Liu

– Exercises classes for the first year of Bachelor program of Ecole polytechnique in the frame-

work of a “Monitorat”.

• Nicolas Vandame

– Exercises classes for the first year of Bachelor program of Ecole polytechnique in the frame-

work of a “Monitorat”.

22

Inria Annual Report 2023

11.2.2 Supervision

• Matìas Bender directed the M2 thesis of Tom Baumbach at the Technische Universität Berlin.

• PhD: Quentin Jacquet, registered at IPP (EDMH) since November 2020, thesis supervisor, Stéphane Gaubert,

co-supervised by Clémence Alasseur and Wim van Ackooij. The defense took place on October 24,
2023.

• PhD: Shanqing Liu, registered at IPP (EDMH) since September 2020, thesis supervisor, Mari-
anne Akian, co-supervised by Stéphane Gaubert. The defense took place on December 22, 2023.

• PhD in progress: Quentin Canu, registered at Univ. Paris Saclay since October 2020, thesis super-
visor: Georges Gonthier (INRIA), cosupervision: Xavier Allamigeon and Pierre-Yves Strub (LIX).

• PhD in progress: Antoine Bereau, registered at IPP (EDMH) since September 2021. Thesis super-

visor: Stéphane Gaubert, cosupervision: Marianne Akian.

• PhD in progress: Nicolas Vandame, registered at IPP (EDMH) since September 2021, thesis super-

visor: Stéphane Gaubert, cosupervision: Xavier Allamigeon.

• PhD in progress: Amanda Bigel, registered at IPP (EDMH) since September 2022, main thesis

supervisors: Cormac Walsh et Constantin Vernicos, thesis supervisor: Stéphane Gaubert.

• PhD in progress: Loic Marchesini, registered at IPP (EDMH), since September 2023. Thesis super-

visor Marianne Akian, co-supervised by Stéphane Gaubert.

• PhD in progress: Pascal Capetillo, registered at IPP (EDMH), since November 2023. Thesis super-

visor: Stéphane Gaubert, cosupervision: Xavier Allamigeon.

• PhD in progress: Jonathan Hornewall, registered at Marne-la-vallée, ENPC (maths and STIC), since

November 2023. Thesis supervisor: Vincent Leclere, cosupervision: Stéphane Gaubert.

11.2.3 Juries

• Marianne Akian

– Jury (and reviewer) of the HDR of Vincent Leclere, Ecole des Ponts ParisTech, April 17, 2023.

– Jury of the PhD thesis of Christina Katsamaki, Sorbonne Univerity, June 21, 2023.

– Jury of the PhD thesis of Manh Hung LE, Université de Limoges, Dec. 20, 2023.

– Jury of the PhD thesis of Shanqing Liu, Ecole polytechnique, Dec. 22, 2023.

• Stéphane Gaubert

– Member of the HCERES visiting committee of CEREMADE, October 2023.

– Member of “Comité de Sélection” (MdC, Optimization) at Nice, Spring 2023.

– Jury of the PhD thesis of Quentin Jacquet, Ecole polytechnique, October 24, 2023.

– Jury the PhD thesis of Francisco Venegas, University of Chile, July 2023.

11.2.4 Communications at conferences and seminars

• Marianne Akian

– Minisymposium “Équations d’Hamilton-Jacobi-Bellman et de jeux à champ moyen” à SMAI
2023, May 22-26, 2023, Le Gosier en Guadeloupe. Exposé: “A multi-level fast-marching method
for the minimum time problem” (travail avec Stéphane Gaubert et Shanqing Liu).

– 13th ISDG Workshop, June 7-9, 2023, Naples, Italy, Session “Numerics and Theory for Differen-
tial Games, in Memory of Maurizio Falcone”, Talk : “Solving irreducible stochastic mean-payoff
games and entropy games by relative Krasnoselskii-Mann iteration”.

Project TROPICAL

23

– 17th International Conference on Reachability Problems (RP 2023). Talk : “Solving irreducible
stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration”.

• Antoine Béreau:

– Journées nationales de calcul formel, Marseille, March 2023. Talk: “The Nullstellensatz and

Positivstellensatz for Sparse Tropical Polynomial Systems”.

– Rencontres Doctorales Lebesgue 2023, Nantes, April 2023. Exposé: “Un tour d’horizon des

mathématiques tropicales”.

– International Symposium on Symbolic and Algebraic Computation 2023, July 24-27, 2023.
Talk: “The Tropical Nullstenllensatz and Positivstellensatz for Sparse Polynomial Systems”
(work with Marianne Akian and Stéphane Gaubert).

• Stéphane Gaubert:

– 48TH International symposium on mathematical foundations of computer science (MFCS
2023). Talk : “Solving irreducible stochastic mean-payoff games and entropy games by relative
Krasnoselskii-Mann iteration”.

– Seminar of of the Dyogene INRIA Team, “Nonarchimedean convexity and applications”, April

2023.

– Seminar of the verification group at IRIF, “Entropy games”, May 2023.

• Shanqing Liu:

– IFAC World Congress 2023, Yokohama, Japan. Talk: “An Adaptive Multi-Level Max-Plus Method

for Deterministic Optimal Control Problems”.

– PGMO days, Palaiseau, November 2023. Talk: “Semiconcave Dual Dynamic Programming
and Its Application to N-body Problems” (work with Marianne Akian, Stéphane Gaubert and
Yang Qi).

• Cormac Walsh:

– “Positivity XI”, Ljubljana, Slovenia, 10–14 July 2023. Talk: “Hilbert geometries isometric to

Banach spaces”.

12 Scientific production

12.1 Major publications

[1] M. Akian, S. Gaubert and A. Guterman. ‘Tropical polyhedra are equivalent to mean payoff games’.
In: Internat. J. Algebra Comput. 22.1 (2012), pp. 1250001, 43. DOI: 10.1142/S0218196711006674.
eprint: 0912.2462. URL: http://dx.doi.org/10.1142/S0218196711006674.

[2] M. Akian, S. Gaubert and R. Nussbaum. ‘Uniqueness of the fixed point of nonexpansive semidif-
ferentiable maps’. In: Transactions of the American Mathematical Society 368.2 (Feb. 2016). Also
arXiv:1201.1536. DOI: 10.1090/S0002-9947-2015-06413-7. URL: https://hal.inria.fr/h
al-00783682.

[3] M. Akian, S. Gaubert and R. Bapat. ‘Non-archimedean valuations of eigenvalues of matrix polyno-
mials’. In: Linear Algebra and its Applications 498 (June 2016). Also arXiv:1601.00438, pp. 592–627.
DOI: 10.1016/j.laa.2016.02.036. URL: https://hal.inria.fr/hal-01251803.

[4] M. Akian, S. Gaubert and C. Walsh. ‘The max-plus Martin boundary’. In: Doc. Math. 14 (2009),

pp. 195–240.

[5] X. Allamigeon, P. Benchimol, S. Gaubert and M. Joswig. ‘Combinatorial simplex algorithms can
solve mean payoff games’. In: SIAM J. Opt. 24.4 (2015), pp. 2096–2117. eprint: 1309.5925.

24

Inria Annual Report 2023

[6] X. Allamigeon, S. Gaubert, E. Goubault, S. Putot and N. Stott. ‘A scalable algebraic method to
infer quadratic invariants of switched systems’. In: Proceedings of the International Conference on
Embedded Software (EMSOFT). Best paper award. The extended version of this conference article
appeared in ACM Trans. Embed. Comput. Syst., 15(4):69:1–69:20, September 2016. 2015.

[7] X. Allamigeon, P. Benchimol, S. Gaubert and M. Joswig. ‘What Tropical Geometry Tells Us about
the Complexity of Linear Programming’. In: SIAM Review 63.1 (4th Feb. 2021), pp. 123–164. DOI:
10.1137/20M1380211. URL: https://hal.inria.fr/hal-03505719.

[8]

J. Bolte, S. Gaubert and G. Vigeral. ‘Definable zero-sum stochastic games’. In: Mathematics of
Operations Research 40.1 (2014). Also arxiv1301.1967, pp. 171–191. DOI: 10.1287/moor.2014.06
66. URL: http://dx.doi.org/10.1287/moor.2014.0666.

[9] S. Friedland, S. Gaubert and L. Han. ‘Perron–Frobenius theorem for nonnegative multilinear
forms and extensions’. In: Linear Algebra and its Applications 438.2 (2013), pp. 738–749. DOI:
10.1016/j.laa.2011.02.042. URL: https://hal.inria.fr/hal-00782755.

[10]

[11]

S. Gaubert and T. Lepoutre. ‘Discrete limit and monotonicity properties of the Floquet eigenvalue
in an age structured cell division cycle model’. In: J. Math. Biol. (2015). DOI: 10.1007/s00285-01
5-0874-3. eprint: 1301.2151. URL: http://dx.doi.org/10.1007/s00285-015-0874-3.

S. Gaubert and G. Vigeral. ‘A maximin characterization of the escape rate of nonexpansive map-
pings in metrically convex spaces’. In: Math. Proc. of Cambridge Phil. Soc. 152 (2012). https://a
rxiv.org/abs/1012.4765, pp. 341–363. URL: http://dx.doi.org/10.1017/S03050041110
00673.

[12] C. Walsh. ‘The horofunction boundary and isometry group of the Hilbert geometry’. In: Handbook
of Hilbert Geometry. Vol. 22. IRMA Lectures in Mathematics and Theoretical Physics. European
Mathematical Society, 2014. URL: https://hal.inria.fr/hal-00782827.

12.2 Publications of the year

International journals

[13] M. Akian, S. Gaubert and L. Rowen. ‘Semiring systems arising from hyperrings’. In: Journal of Pure
and Applied Algebra 228.6 (June 2024), p. 107584. DOI: 10.1016/j.jpaa.2023.107584. URL:
https://inria.hal.science/hal-03792658.

[14] M. Akian, S. Gaubert, Y. Qi and O. Saadi. ‘Tropical linear regression and mean payoff games:
or, how to measure the distance to equilibria’. In: SIAM Journal on Discrete Mathematics 37.2
(24th May 2023), pp. 632–674. DOI: 10.1137/21M1428297. URL: https://inria.hal.science
/hal-03504875.

[15] X. Allamigeon, S. Gaubert and F. Meunier. ‘Tropical Complementarity Problems and Nash Equilib-
ria’. In: SIAM Journal on Discrete Mathematics 37.3 (3rd Aug. 2023), pp. 1645–1665. DOI: 10.1137
/21M1446861. URL: https://hal.science/hal-04355016.

[16] Q. Jacquet, W. van Ackooij, C. Alasseur and S. Gaubert. ‘Quadratic regularization of bilevel pricing
problems and application to electricity retail markets’. In: European Journal of Operational Re-
search 313.3 (Mar. 2024), pp. 841–857. DOI: 10.1016/j.ejor.2023.05.006. URL: https://inr
ia.hal.science/hal-03504874.

International peer-reviewed conferences

[17] M. Akian, A. Béreau and S. Gaubert. ‘The Tropical Nullstellensatz and Positivstellensatz for Sparse
Polynomial Systems’. In: ISSAC ’23: Proceedings of the 2023 International Symposium on Symbolic
and Algebraic Computation. ISSAC 2023 - International Symposium on Symbolic and Algebraic
Computation. Tromsø, Norway: ACM, 2023. DOI: 10.1145/3597066.3597089. URL: https://i
nria.hal.science/hal-04117544.

[18] M. Akian, S. Gaubert and S. Liu. ‘An Adaptive Multi-Level Max-Plus Method for Deterministic
Optimal Control Problems’. In: Proceedings of the 22nd IFAC World Congress. IFAC World Congress
2023. Yokohama, Japan, 9th July 2023. URL: https://inria.hal.science/hal-04406978.

Project TROPICAL

25

[19] M. Akian, S. Gaubert, U. Naepels and B. Terver. ‘Solving Irreducible Stochastic Mean-Payoff Games
and Entropy Games by Relative Krasnoselskii-Mann Iteration’. In: MFCS 2023 - 48th International
Symposium on Mathematical Foundations of Computer Science. Vol. 272. Bordeaux, France:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 28th Aug. 2023. DOI: 10 . 4230 / LIPIcs
.MFCS.2023.10. URL: https://inria.hal.science/hal-04365602.

[20] X. Allamigeon, Q. Canu and P.-Y. Strub. ‘A Formal Disproof of Hirsch Conjecture’. In: Proceedings
of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs. CPP 2023 -
12th ACM SIGPLAN International Conference on Certified Programs and Proofs. Boston, United
States: ACM, 11th Jan. 2023, pp. 17–29. DOI: 10.1145/3573105.3575678. URL: https://inria
.hal.science/hal-04368266.

[21] Q. Jacquet, W. van Ackooij, C. Alasseur and S. Gaubert. ‘A Quantization Procedure for Nonlinear
Pricing with an Application to Electricity Markets’. In: Proceedings of IEEE CDC 2023. 62nd IEEE
Conference on Decision and Control. Singapore (SG), Singapore, 13th Dec. 2023. URL: https://h
al.science/hal-04052232.

Reports & preprints

[22] M. Akian, X. Allamigeon, S. Gaubert and S. Sergeev. Signed tropicalization of polar cones. 28th Dec.

2023. URL: https://inria.hal.science/hal-04365674.

[23] M. Akian, A. Béreau and S. Gaubert. The Nullstellensatz and Positivstellensatz for Sparse Tropical
Polynomial Systems. 10th Dec. 2023. URL: https://inria.hal.science/hal-04333931.

[24] M. Akian, S. Gaubert and L. Rowen. Linear algebra over T-pairs. 8th Oct. 2023. URL: https://inr

ia.hal.science/hal-04406848.

[25] M. Akian, S. Gaubert and H. Tavakolipour. Factorization of polynomials over the symmetrized
tropical semiring and Descartes’ rule of sign over ordered valued fields. 13th Jan. 2023. URL: https:
//inria.hal.science/hal-03941832.

[26] M. Akian, S. Gaubert and S. Liu. A Multi-Level Fast-Marching Method For The Minimum Time

Problem. 19th Mar. 2023. URL: https://inria.hal.science/hal-04365665.

[27] M. Akian, S. Gaubert and S. Vannucci. Ambitropical geometry, hyperconvexity and zero-sum games.

6th July 2023. URL: https://inria.hal.science/hal-03504873.

[28] C. Alasseur, E. Bayraktar, R. Dumitrescu and Q. Jacquet. A Rank-Based Reward between a Principal
and a Field of Agents: Application to Energy Savings. 31st July 2023. URL: https://hal.science
/hal-03770115.

[29] X. Allamigeon, Q. Canu, C. Cohen, K. Sakaguchi and P.-Y. Strub. Design patterns of hierarchies for

order structures. 28th Feb. 2023. URL: https://inria.hal.science/hal-04008820.

[30] M. R. Bender and P.-J. Spaenlehauer. Dimension results for extremal-generic polynomial systems
over complete toric varieties. 12th May 2023. URL: https://inria.hal.science/hal-0410256
4.

[31] P. Cannarsa, S. Gaubert, C. Mendico and M. Quincampoix. Analysis of the vanishing discount limit
for optimal control problems in continuous and discrete time. 12th June 2023. URL: https://inri
a.hal.science/hal-04365643.

[32] D. Faifman, C. Vernicos and C. Walsh. Volume growth of Funk geometry and the flags of polytopes.

15th June 2023. URL: https://hal.science/hal-04403794.

[33]

S. Friedland and S. Gaubert. Bit-complexity estimates in geometric programming, and application
to the polynomial-time computation of the spectral radius of nonnegative tensors. 25th Jan. 2023.
URL: https://inria.hal.science/hal-04365626.

[34] K. Kozhasov, A. Muniz, Y. Qi and L. Sodomaco. On the minimal algebraic complexity of the rank-
one approximation problem for general inner products. 26th Sept. 2023. URL: https://inria.ha
l.science/hal-04408246.

26

Inria Annual Report 2023

12.3 Cited publications

[35] X. Allamigeon, M. Boyet and S. Gaubert. ‘Piecewise Affine Dynamical Models of Timed Petri Nets –
Application to Emergency Call Centers’. In: Fundamenta Informaticae 183.3-4 (2021), pp. 169–201.
URL: https://hal.archives-ouvertes.fr/hal-02550006.

[36] X. Allamigeon, S. Gaubert and M. Skomra. ‘Tropical spectrahedra’. In: Discrete and Computational
Geometry 63 (Feb. 2020), pp. 507–548. DOI: 10.1007/s00454-020-00176-1. URL: https://hal
.inria.fr/hal-01422639.

[37] M. Akian, J.-P. Chancelier, L. Pascal and B. Tran. ‘Tropical numerical methods for solving stochastic
control problems’. In: MTNS 2022 - 25th International Symposium on Mathematical Theory of
Networks and Systems. Bayreuth (DE), Germany, 12th Sept. 2022. URL: https://hal.inria.fr
/hal-03944216.

[38] X. Allamigeon, M. Boyet and S. Gaubert. ‘Computing Transience Bounds of Emergency Call
Centers: a Hierarchical Timed Petri Net Approach’. In: PETRI NETS 2022: Application and Theory
of Petri Nets and Concurrency. Vol. 13288. PETRI NETS 2022: Application and Theory of Petri Nets
and Concurrency, Springer Lecture Notes in Computer Sciences. Bergen, Norway: Springer, 2022,
pp. 90–112. DOI: 10.1007/978-3-031-06653-5_5. URL: https://hal.inria.fr/hal-03913
405.

[39] X. Allamigeon, D. Dadush, G. Loho, B. Natura and L. Vegh. ‘Interior point methods are not worse
than Simplex’. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science
(FOCS). Denver, United States: IEEE, 31st Oct. 2022, pp. 267–277. DOI: 10.1109/FOCS54457.202
2.00032. URL: https://hal.inria.fr/hal-03915650.

[40] X. Allamigeon, S. Gaubert and N. Vandame. ‘No self-concordant barrier interior point method
is strongly polynomial’. In: STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Com-
puting. Rome Italy, France: ACM, 20th June 2022, pp. 515–528. DOI: 10.1145/3519935.3519997.
URL: https://hal.inria.fr/hal-03915670.

[41] Q. Jacquet, W. van Ackooij, C. Alasseur and S. Gaubert. ‘Ergodic control of a heterogeneous
population and application to electricity pricing’. In: IEEE CDC 2022. Cancun, Mexico, 6th Dec.
2022. URL: https://hal.science/hal-03629189.

[42] M. Akian, J.-P. Chancelier and B. Tran. Tropical Dynamic Programming for Lipschitz Multistage
Stochastic Programming. 13th Dec. 2020. URL: https://hal.inria.fr/hal-03059701.

[43] X. Allamigeon, A. Aznag, S. Gaubert and Y. Hamdi. The tropicalization of the entropic barrier. 2020.

URL: https://hal.archives-ouvertes.fr/hal-03151661.

[44] X. Allamigeon, S. Gaubert and F. Meunier. Tropical complementarity problems and Nash equilibria.
v3, Nov. 2022, to appear in SIAM Disc. Math. 2020. URL: https://hal.archives-ouvertes.fr
/hal-03151662.

[45] M. Akian, S. Gaubert and A. Lakhoua. ‘The max-plus finite element method for solving determin-
istic optimal control problems: basic properties and convergence analysis’. In: SIAM J. Control
Optim. 47.2 (2008), pp. 817–848. DOI: 10.1137/060655286. URL: http://www.arxiv.org/abs
/math.OC/0603619.

[46] M. Akian and S. Gaubert. ‘Spectral theorem for convex monotone homogeneous maps, and ergodic
control’. In: Nonlinear Anal. 52.2 (2003), pp. 637–679. DOI: 10.1016/S0362-546X(02)00170-0.
URL: http://dx.doi.org/10.1016/S0362-546X(02)00170-0.

[47] M. Akian, S. Gaubert, J. Grand-Clément and J. Guillaud. ‘The operator approach to entropy games’.
In: Theory of Computing Systems (2019). https://arxiv.org/abs/1904.05151. DOI: 10.1007
/s00224-019-09925-z. URL: https://hal.archives-ouvertes.fr/hal-02143807.

[48] M. Akian, S. Gaubert and A. Hochart. ‘Generic uniqueness of the bias vector of finite stochastic
games with perfect information’. In: Journal of Mathematical Analysis and Applications 457 (2018).
https://arxiv.org/abs/1610.09651, pp. 1038–1064. DOI: 10.1016/j.jmaa.2017.07.017.
URL: https://hal.inria.fr/hal-01425543.

Project TROPICAL

27

[49] M. Akian, S. Gaubert and M. Sharify. ‘Log-majorization of the moduli of the eigenvalues of a matrix
polynomial by tropical roots’. In: Linear Algebra and its Applications (2017). Also arXiv:1304.2967.
DOI: 10.1016/j.laa.2016.11.004. URL: https://hal.inria.fr/hal-00881196.

[50] X. Allamigeon, S. Gaubert and É. Goubault. ‘Inferring Min and Max Invariants Using Max-plus
Polyhedra’. In: Proceedings of the 15th International Static Analysis Symposium (SAS’08). Vol. 5079.
LNCS. Valencia, Spain: Springer, 2008, pp. 189–204. URL: http://dx.doi.org/10.1007/978-3-
540-69166-2_13.

[51] X. Allamigeon, P. Benchimol and S. Gaubert. ‘The tropical shadow-vertex algorithm solves mean
payoff games in polynomial time on average’. In: ICALP 2014. Ed. by J. Esparza, P. Fraigniaud, T.
Husfeldt and E. Koutsoupias. Vol. 8572. 41st International Colloquium, ICALP 2014, Copenhagen,
Denmark, July 8-11, 2014, Proceedings, Part I. Copenhagen, France: Springer, 2014, p. 12. DOI:
10.1007/978-3-662-43948-7_8. URL: https://hal.inria.fr/hal-01096447.

[52] X. Allamigeon, P. Benchimol, S. Gaubert and M. Joswig. ‘Log-barrier interior point methods are
not strongly polynomial’. In: SIAM Journal on Applied Algebra and Geometry 2.1 (2018). https:
//arxiv.org/abs/1708.01544 - This paper supersedes arXiv:1405.4161. 31 pages, 5 figures, 1
table, pp. 140–178. DOI: 10.1137/17M1142132. URL: https://hal.inria.fr/hal-01674959.

[53] X. Allamigeon, V. Boeuf and S. Gaubert. ‘Performance evaluation of an emergency call center:
tropical polynomial systems applied to timed Petri nets’. In: 13th International Conference, Formal
Modeling and Analysis of Timed Systems (FORMATS 2015). Vol. 9268. Formal Modeling and Analysis
of Timed Systems. Madrid, Spain: Springer, 2015. DOI: 10.1007/978-3-319-22975-1_2. URL:
https://hal.inria.fr/hal-01248814.

[54] X. Allamigeon, V. Boeuf and S. Gaubert. ‘Stationary solutions of discrete and continuous Petri nets
with priorities’. In: Performance Evaluation 113 (2017). https://arxiv.org/abs/1612.07661,
pp. 1–12. DOI: 10.1016/j.peva.2017.04.007. URL: https://hal.inria.fr/hal-01674492.

[55] X. Allamigeon, S. Gaubert and M. Skomra. ‘Solving generic nonarchimedean semidefinite pro-
grams using stochastic game algorithms’. In: Journal of Symbolic Computation 85 (2018). An
abridged version of this article appeared in the proceedings of ISSAC 2016, pp. 25–54. DOI: 10.10
16/j.jsc.2017.07.002. URL: https://hal.inria.fr/hal-01674494.

[56] X. Allamigeon, S. Gaubert and E. Goubault. ‘Computing the Vertices of Tropical Polyhedra using
Directed Hypergraphs’. In: Discrete and Computational Geometry 49.2 (2013), pp. 247–279. DOI:
10.1007/s00454-012-9469-6. URL: http://hal.inria.fr/hal-00782862.

[57] E. Asarin, J. Cervelle, A. Degorre, C. Dima, F. Horn and V. Kozyakin. ‘Entropy Games and Matrix
Multiplication Games’. In: Proceedings of the 33rd International Symposium on Theoretical Aspects
of Computer Science (STACS). Vol. 47. LIPIcs. Leibniz Int. Proc. Inform. Wadern: Schloss Dagstuhl–
Leibniz-Zentrum für Informatik, 2016, 11:1–11:14.

[58] F. Baccelli, G. Cohen, G.-J. Olsder and J.-P. Quadrat. Synchronization and linearity: an algebra for

discrete event systems. Wiley, 1992.

[59] M. Baker and O. Lorscheid. ‘Descartes’ rule of signs, Newton polygons, and polynomials over
hyperfields’. In: J. Algebra 569 (2021), pp. 416–441. DOI: 10.1016/j.jalgebra.2020.10.024.
URL: https://doi.org/10.1016/j.jalgebra.2020.10.024.

[60] G. Barles, S. Mirrahimi and B. Perthame. ‘Concentration in Lotka-Volterra parabolic or integral
equations: a general convergence result’. In: Methods Appl. Anal. 16.3 (2009), pp. 321–340. DOI:
10.4310/MAA.2009.v16.n3.a4. URL: http://dx.doi.org/10.4310/MAA.2009.v16.n3.a4.

[61] V. Boeuf and P. Robert. ‘A Stochastic Analysis of a Network with Two Levels of Service’. In: Queueing
Systems 92.3-4 (2019). https://arxiv.org/abs/1708.09590, p. 30. DOI: 10.1007/s11134-01
9-09617-y. URL: https://hal.archives-ouvertes.fr/hal-01583704.

[62] F. Bonnans and S. Gaubert. Recherche opérationnelle. Aspects mathématiques et applications.

Ellipse, 2016, p. 391. URL: https://hal.inria.fr/hal-01422645.

[63] M. Boyet. ‘Piecewise affine dynamical systems applied to the performance evaluation of emer-
gency call centers’. PhD thesis. Ecole polytechnique, 2022. URL: http://www.cmapx.polytechn
ique.fr/~marin.boyet/These_MB.pdf.

28

Inria Annual Report 2023

[64] P. Butkoviˇc. ‘Max-algebra: the linear algebra of combinatorics?’ In: Linear Algebra and its applica-

tions 367 (2003), pp. 313–335.

[65] P. Butkoviˇc. Max-linear systems: theory and algorithms. Springer Monographs in Mathematics.
Springer-Verlag London, Ltd., London, 2010, pp. xviii+272. DOI: 10.1007/978-1-84996-299-5.
URL: http://dx.doi.org/10.1007/978-1-84996-299-5.

[66]

J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. Mc Gettrick and J.-P. Quadrat. ‘Numerical computa-
tion of spectral elements in max-plus algebra’. In: Proc. of the IFAC Conference on System Structure
and Control. Nantes, 1998.

[67] G. Cohen, S. Gaubert and J.-P. Quadrat. ‘Max-plus algebra and system theory: where we are and

where to go now’. In: Annual Reviews in Control 23 (1999), pp. 207–219.

[68] A. Connes and C. Consani. ‘Geometry of the arithmetic site’. In: Adv. Math. 291 (2016), pp. 274–

329.

[69] P. Cousot and R. Cousot. ‘Abstract Interpretation: A unified lattice model for static analysis of
programs by construction of approximations of fixed points’. In: Principles of Programming
Languages 4 (1977), pp. 238–252.

[70] D. Delling, P. Sanders, D. Schultes and D. Wagner. ‘Highway hierarchies star’. In: The shortest path
problem. Vol. 74. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Amer. Math. Soc., Providence,
RI, 2009, pp. 141–174.

[71] A. Fathi and A. Siconolfi. ‘Existence of C 1 critical subsolutions of the Hamilton-Jacobi equation’.
In: Invent. Math. 155.2 (2004), pp. 363–388. DOI: 10.1007/s00222-003-0323-6. URL: http://d
x.doi.org/10.1007/s00222-003-0323-6.

[72] O. Fercoq, M. Akian, M. Bouhtou and S. Gaubert. ‘Ergodic control and polyhedral approaches to
PageRank optimization’. In: IEEE Trans. Automat. Control 58.1 (2013), pp. 134–148. DOI: 10.1109
/TAC.2012.2226103. URL: http://dx.doi.org/10.1109/TAC.2012.2226103.

[73] W. Fleming and W. McEneaney. ‘A max-plus based algorithm for an HJB equation of non-linear

filtering’. In: SIAM J. Control and Opt. (2000), pp. 683–710.

[74]

S. Fomin and A. Zelevinsky. ‘Cluster algebras. I. Foundations’. In: J. Amer. Math. Soc. 15.2 (2002),
pp. 497–529. URL: http://arxiv.org/abs/math.RT/0104151.

[75] S. Gaubert, E. Goubault, A. Taly and S. Zennou. ‘Static Analysis by Policy Iteration in Relational
Domains’. In: Proceedings of the Proc. of the 16th European Symposium on Programming (ESOP’07).
Vol. 4421. LNCS. Braga (Portugal): Springer, 2007, pp. 237–252. DOI: 10.1007/978-3-540-71316
-6_17. URL: http://dx.doi.org/10.1007/978-3-540-71316-6_17.

[76] S. Gaubert, W. McEneaney and Z. Qu. ‘Curse of dimensionality reduction in max-plus based
approximation methods: theoretical estimates and improved pruning algorithms’. In: Proceedings
of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC
11). Orlando, FL, USA, 2011, pp. 1054–1061. URL: http://arxiv.org/abs/1109.5241.

[77]

S. Gaubert and M. Sharify. ‘Tropical scaling of polynomial matrices’. In: Positive systems. Vol. 389.
Lecture Notes in Control and Inform. Sci. Berlin: Springer, 2009, pp. 291–303. URL: http://dx.do
i.org/10.1007/978-3-642-02894-6_28.

[78] T. M. Gawlitza, H. Seidl, A. Adjé, S. Gaubert and E. Goubault. ‘Abstract interpretation meets convex
optimization’. In: J. Symbolic Comput. 47.12 (2012). Special issue on Invariant generation and
reasoning about loops, pp. 1416–1446. DOI: 10.1016/j.jsc.2011.12.048. URL: http://dx.do
i.org/10.1016/j.jsc.2011.12.048.

[79]

I. M. Gelfand, M. M. Kapranov and A. V. Zelevinsky. Discriminants, resultants and multidimen-
sional determinants. Modern Birkhäuser Classics. Reprint of the 1994 edition. Birkhäuser Boston,
Inc., Boston, MA, 2008, pp. x+523.

[80] T. Haettel, A.-S. Schilling, A. Wienhard and C. Walsh. ‘Horofunction Compactifications of Sym-
metric Spaces’. https://arxiv.org/abs/1705.05026 - working paper or preprint. 2018. URL:
https://hal.archives-ouvertes.fr/hal-01814137.

Project TROPICAL

29

[81] S. Hammarling, C. J. Munro and F. Tisseur. ‘An algorithm for the complete solution of quadratic
eigenvalue problems’. In: ACM Trans. Math. Software 39.3 (2013), Art. 18, 19. DOI: 10.1145/2450
153.2450156. URL: http://dx.doi.org/10.1145/2450153.2450156.

[82] B. Heidergott, G. J. Olsder and J. van der Woude. Max Plus at Work: Modeling and Analysis of
Synchronized Systems: A Course on Max-Plus Algebra and Its Applications. Princeton, 2005.

[83] H. Ishii and H. Mitake. ‘Representation formulas for solutions of Hamilton-Jacobi equations with
convex Hamiltonians’. In: Indiana Univ. Math. J. 56.5 (2007), pp. 2159–2183. DOI: 10.1512/iumj
.2007.56.3048. URL: http://dx.doi.org/10.1512/iumj.2007.56.3048.

[84]

I. Itenberg, G. Mikhalkin and E. Shustin. Tropical algebraic geometry. Vol. 35. Oberwolfach Sem-
inars. Basel: Birkhäuser Verlag, 2007, pp. viii+103.

[85] Q. Jacquet. ‘Stackelberg games, optimal pricing and application to electricity markets’. Theses.
Institut Polytechnique de Paris, Oct. 2023. URL: https://theses.hal.science/tel-0429918
2.

[86] V. Kolokoltsov and V. Maslov. Idempotent analysis and applications. Kluwer Acad. Publisher, 1997.

[87] H. Kurniawati, D. Hsu and W. S. Lee. ‘Sarsop: Efficient point-based pomdp planning by approx-
imating optimally reachable belief spaces.’ In: Robotics: Science and systems. Vol. 2008. Zurich,
Switzerland. 2008.

[88] B. Lemmens and R. Nussbaum. Nonlinear Perron-Frobenius theory. Vol. 189. Cambridge Tracts in
Mathematics. Cambridge University Press, Cambridge, 2012, pp. xii+323. DOI: 10.1017/CBO9781
139026079. URL: http://dx.doi.org/10.1017/CBO9781139026079.

[89]

S. Liu. ‘Highway Hierarchies for HJB Equations’. PhD thesis. Ecole polytechnique, Dec. 2023.

[90] Q. Lu, M. Madsen, M. Milata, S. Ravn, U. Fahrenberg and K. G. Larsen. ‘Reachability Analysis for
Timed Automata using Max-Plus Algebra’. In: J. Logic Alg. Prog. 81.3 (2012), pp. 298–313.

[91] V. Maslov. Méthodes Operatorielles. Moscou: Edition Mir, 1987.

[92] W. M. McEneaney. ‘A curse-of-dimensionality-free numerical method for solution of certain HJB
PDEs’. In: SIAM J. Control Optim. 46.4 (2007), pp. 1239–1276. DOI: 10.1137/040610830. URL:
http://dx.doi.org/10.1137/040610830.

[93] W. McEneaney, A. Deshpande and S. Gaubert. ‘Curse-of-Complexity Attenuation in the Curse-of-
Dimensionality-Free Method for HJB PDEs’. In: Proc. of the 2008 American Control Conference.
Seattle, Washington, USA, 2008.

[94] W. M. McEneaney. Max-plus methods for nonlinear control and estimation. Systems & Control:

Foundations & Applications. Boston, MA: Birkhäuser Boston Inc., 2006, pp. xiv+241.

J.-F. Mertens, S. Sorin and S. Zamir. Repeated Games. Cambridge, 2015.

[95]
[96] G. Mikhalkin. ‘Enumerative tropical algebraic geometry in R2’. In: J. Amer. Math. Soc. 18.2 (2005),
pp. 313–377. DOI: 10.1090/S0894-0347-05-00477-7. URL: http://dx.doi.org/10.1090
/S0894-0347-05-00477-7.

[97] R. H. Möhring, M. Skutella and F. Stork. ‘Scheduling with AND/OR precedence constraints’. In:
SIAM J. Comput. 33.2 (2004), pp. 393–415. DOI: 10.1137/S009753970037727X. URL: http://dx
.doi.org/10.1137/S009753970037727X.

[98] A. Papadopoulos. Metric spaces, convexity and non-positive curvature. Second. Vol. 6. IRMA
Lectures in Mathematics and Theoretical Physics. European Mathematical Society (EMS), Zürich,
2014, pp. xii+309. DOI: 10.4171/132. URL: http://dx.doi.org/10.4171/132.

[99] M. V. F. Pereira and L. M. V. G. Pinto. ‘Multi-stage stochastic optimization applied to energy
planning’. In: Math. Programming 52.2, Ser. B (1991), pp. 359–375. DOI: 10.1007/BF01582895.
URL: http://dx.doi.org/10.1007/BF01582895.

[100]

[101]

J.-E. Pin. ‘Tropical Semirings’. In: Idempotency. Ed. by J. Gunawardena. Vol. 11. Publications of the
Isaac Newton Institute. Cambridge University Press, 1998, pp. 50–69.

J. Pineau, G. Gordon, S. Thrun et al. ‘Point-based value iteration: An anytime algorithm for
POMDPs’. In: IJCAI. Vol. 3. 2003, pp. 1025–1032.

30

Inria Annual Report 2023

[102] M. Plus. ‘Linear systems in (max,+) algebra’. In: Proceedings of the 29th IEEE Conference on Decision

and Control. IEEE. 1990, pp. 151–156.

[103] Z. Qu. ‘Théorie de Perron-Frobenius non linéaire et méthodes numériques max-plus pour la
résolution d’équations d’Hamilton-Jacobi’. PhD thesis. Ecole Polytechnique X, 2013. URL: http:
//hal.inria.fr/pastel-00927122.

[104] D. Reeb, M. J. Kastoryano and M. M. Wolf. ‘Hilbert’s projective metric in quantum information
theory’. In: J. Math. Phys. 52.8 (2011), pp. 082201, 33. DOI: 10.1063/1.3615729. URL: http://dx
.doi.org/10.1063/1.3615729.

[105]

J. Richter-Gebert, B. Sturmfels and T. Theobald. ‘First steps in tropical geometry’. In: Idempotent
mathematics and mathematical physics. Vol. 377. Contemp. Math. Providence, RI: Amer. Math.
Soc., 2005, pp. 289–317.

[106] G. Sagnol, S. Gaubert and M. Bouhtou. ‘Optimal monitoring on large networks by Successive c-
Optimal Designs’. In: Proceedings of the 22nd international teletraffic congress (ITC22), Amsterdam,
The Netherlands, September. http://dx.doi.org/10.1109/ITC.2010.5608717. IEEE, 2010.

[107] P. Sanders and D. Schultes. ‘Engineering highway hierarchies’. In: ACM J. Exp. Algorithmics 17
(2012), Article 1.6, 40. DOI: 10.1145/2133803.2330080. URL: https://doi.org/10.1145/213
3803.2330080.

[108] S. Sankaranarayanan, H. Sipma and Z. Manna. ‘Scalable Analysis of Linear Systems using Math-

ematical Programming’. In: VMCAI. Vol. 3385. LNCS. 2005.

[109] R. Sepulchre, A. Sarlette and P. Rouchon. ‘Consensus in noncommutative spaces’. Anglais. In:
Proceedings of the 49th IEEE Conference on Decision and Control. Atlanta, USA, 2010, pp. 6596–
6601. URL: http://dx.doi.org/10.1109/CDC.2010.5717072.

[110] G. Shani, J. Pineau and R. Kaplow. ‘A survey of point-based POMDP solvers’. In: Autonomous

Agents and Multi-Agent Systems 27.1 (2013), pp. 1–51.

[111]

I. Simon. ‘Limited subsets of a free monoid’. In: Proc. 19th Annual Symposium on Foundations of
Computer Science. Piscataway, NJ, 1978, pp. 143–150.

[112] H. L. Smith. Monotone dynamical systems. Vol. 41. Mathematical Surveys and Monographs. An
introduction to the theory of competitive and cooperative systems. American Mathematical
Society, Providence, RI, 1995, pp. x+174.

[113] D.-N. Tran. ‘Programmation dynamique tropicale en optimisation stochastique multi-étapes’.
Theses. Université Paris-Est, 2020. URL: https://pastel.archives-ouvertes.fr/tel-0312
9146.

[114] N. M. Tran and J. Yu. ‘Product-Mix Auctions and Tropical Geometry’. In: Math. O.R. 44.4 (2019).

arXiv:1505.05737, pp. 1396–1411.

[115] O. Viro. ‘Dequantization of real algebraic geometry on logarithmic paper’. In: European Congress of
Mathematics, Vol. I (Barcelona, 2000). Vol. 201. Progr. Math. Basel: Birkhäuser, 2001, pp. 135–146.
<scratchpad>
- Main topic: Research Centre TROPICAL, focusing on tropical methods in applied mathematics, optimization, and control.
- Key points:
  - Tropical methods for structures, algorithms, and interactions in applied mathematics.
  - Optimization and control of dynamic systems using tropical algebra tools.
  - Applications in decision theory, discrete event systems, and verification of programs and systems.
  - Research program includes optimal control, zero-sum games, and non-linear Perron-Frobenius theory.
  - Algebraic aspects of tensors and complexity theory.
- Structure: The document is organized into sections, including Activity Report, Project-Team, Domain, Theme, Research Program, Application Domains, Social and Environmental Responsibility, Highlights of the Year, New Software, New Results, Bilateral Contracts and Grants with Industry, Partnerships and Cooperations, Dissemination, Scientific Production, and References.
- Potential artifacts to ignore: Links, HTML tags, and web-related elements.
</scratchpad>

<final_summary>
The TROPICAL research centre focuses on tropical methods in applied mathematics, optimization, and control. Tropical methods are used to analyze and optimize dynamic systems, with applications in decision theory, discrete event systems, and verification of programs and systems. The research program includes optimal control, zero-sum games, and non-linear Perron-Frobenius theory, with connections to algebraic aspects of tensors and complexity theory. The centre's work has significant implications for fields such as optimization, control, and decision theory, and has led to the development of new software and platforms, including Coq-Polyhedra and EmergencyEval. The centre's research has also been recognized through various awards and publications, highlighting its impact on the field of applied mathematics and its applications.
The TROPICAL research centre focuses on tropical methods in applied mathematics, optimization, and control. Tropical methods are used to analyze and optimize dynamic systems, with applications in decision theory, discrete event systems, and verification of programs and systems. The research program includes optimal control, zero-sum games, and non-linear Perron-Frobenius theory, with connections to algebraic aspects of tensors and complexity theory. The centre's work has significant implications for fields such as optimization, control, and decision theory, and has led to the development of new software and platforms, including Coq-Polyhedra and EmergencyEval. The centre's research has also been recognized through various awards and publications, highlighting its impact on the field of applied mathematics and its applications.