In classical optimization, linear programming relies on the smooth, continuous geometry of vector spaces over fields like $\mathbb{R}$. But what happens if we redefine the arithmetic operations themselves? In the tropical semiring ($\mathbb{R} \cup \{-\infty\}$), standard addition is replaced by maximization ($\max$), and standard multiplication is replaced by addition ($+$).
In this setting, traditional calculus and linear algebra break down because there are no additive inverses—you cannot subtract to isolate a variable. Yet, optimization problems with min-max structures—such as those found in static program analysis, scheduling, and game theory—naturally map to this framework.
Historically, solving a tropical linear program (TLP) required "lifting" the problem to a highly complex non-Archimedean field (like Puiseux series), solving it using classical methods, and projecting the result back. This process is computationally intensive and obscures the underlying discrete geometry. The breakthrough in this field is the development of tropical simplex algorithms that operate directly within tropical arithmetic, bypassing field extensions entirely.
The Combinatorial Geometry of Tropical Polyhedra
To understand how a tropical simplex algorithm can pivot without subtraction, we must first look at the geometry of tropical polyhedra. In classical geometry, a polyhedron is an intersection of half-spaces bounded by flat hyperplanes. In tropical geometry, a "hyperplane" is the set of points where a tropical linear polynomial attains its maximum at least twice. This requirement splits the space into regions, turning tropical polyhedra into rigid, spider-like combinatorial structures made of classical polyhedral cones.
To compute the internal representations (extreme points and rays) of these structures, Allamigeon et al. introduced the tropical double description method. Rather than relying on standard matrix inversions, the geometry here is fundamentally graph-theoretic.
As shown by Allamigeon et al. in Computing the Vertices of Tropical Polyhedra Using Directed Hypergraphs, the vertices of tropical polyhedra can be completely characterized and computed using directed hypergraphs. Similarly, Loho and Joswig demonstrated in Weighted digraphs and tropical cones that tropical cones are intimately tied to the paths and cycles of weighted directed graphs. This graph-theoretic backbone replaces the traditional notion of a vector space basis.
Classical Linear Programming Tropical Linear Programming
[ Smooth Vector Spaces ] [ Weighted Digraphs / Cones ]
│ │
▼ ▼
Matrix Inversion & Pivoting Combinatorial Graph Pivoting
Pivoting Without Subtraction
The classical simplex algorithm moves from vertex to vertex along the edges of a polyhedron by performing pivoting operations (Gaussian elimination) to find an adjacent basis. In the tropical semiring, because we cannot subtract, we cannot eliminate variables in the traditional sense.
The solution lies in combinatorial pivoting rules. Instead of tracking numerical values through matrix arithmetic, the algorithm tracks the combinatorial state of an underlying graph or matroid. In Tropicalizing the Simplex Algorithm, Allamigeon et al. designed a simplex method that operates entirely within tropical arithmetic. By focusing on the signs of the minors of the constraint matrix, they showed that each pivoting step takes $O(n(m+n))$ time—matching the efficiency of classical simplex implementations.
To abstract this mechanism further, Loho developed a framework based on signed tropical matroids in Abstract Tropical Linear Programming. Here, the simplex algorithm is re-envisioned as a sequence of pivots through bipartite graphs, linking algorithmic complexity directly to the geometric properties of secondary fans. This combinatorial abstraction provides a discrete analogue for studying the limits of pivoting methods, offering a new path toward solving the long-standing open question of finding a strongly polynomial algorithm for linear programming.
The Equivalence to Mean Payoff Games
Why do these tropical algorithms work so effectively, and what makes them so valuable? The answer lies in a remarkable, exact equivalence between tropical geometry and game theory.
In Tropical Polyhedra are Equivalent to mean Payoff Games, Akian et al. proved that decision problems over tropical polyhedra are mathematically equivalent to solving mean payoff games (two-player, infinite-horizon, zero-sum games on graphs). When a tropical simplex algorithm moves along the edges of a tropical polyhedron, it is implicitly navigating the strategy space of a mean payoff game.
This connection yields powerful algorithmic insights in both directions:
- From Games to Optimization: Gaubert et al. developed a Newton-like algorithm for tropical linear-fractional programming by iteratively computing a "tropical derivative" using player strategies, reducing the problem to a sequence of simple, one-player shortest-path games.
- From Optimization to Games: In The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average, Allamigeon et al. adapted the classical shadow-vertex pivoting rule to the max-plus semiring. They proved that this tropicalized algorithm solves mean payoff games in polynomial time on average. Because individual pivoting steps are equivalent to solving optimal assignment problems, the computational overhead remains low, making it highly practical.
Overcoming Degeneracy
In classical linear programming, degeneracy occurs when more constraints than necessary meet at a single vertex, which can cause the simplex algorithm to cycle indefinitely without making progress. Tropical linear programs are inherently and severely degenerate because the $\max$ operator forces multiple terms to achieve the exact same maximum value simultaneously.
To make the tropical simplex algorithm robust, Allamigeon et al. introduced a symbolic perturbation scheme and a Phase I algorithm in Combinatorial Simplex Algorithms Can Solve Mean Payoff Games. By embedding a degenerate tropical polyhedron into a larger, guaranteed non-degenerate structure, the algorithm can reliably find an initial feasible basis and execute valid simplex steps without getting stuck in infinite loops. This combination of symbolic perturbation and combinatorial pivoting bridges the gap between theoretical tropical geometry and effective, implementable optimization tools.
Key Foundational Work
Tropical linear-fractional programming and parametric mean payoff games (2012) — contributed 5 concept elements to this direction.
Tropical Polyhedra are Equivalent to mean Payoff Games (2012) — contributed 1 concept elements to this direction.
The tropical double description method (2010) — contributed 1 concept elements to this direction.