TL;DR
The authors introduce a tropical geometry analogue of the classical double description method to convert a tropical polyhedron from an external representation (systems of max-plus inequalities) into an internal one (generators and extreme rays). By mapping the redundancy check of candidate rays to reachability in directed hypergraphs, the algorithm tests extremality in almost-linear time. This eliminates combinatorial bottlenecks, yielding speedups of several orders of magnitude over prior tropical algorithms.
What Problem Does This Paper Address?
In tropical algebra (or max-plus algebra), addition is defined as $x \oplus y := \max(x, y)$ and multiplication as $x \otimes y := x + y$. Tropical polyhedra are the max-plus counterparts to classical convex polyhedra. Just like their Euclidean cousins, they can be described either:
- Externally, as the solution set of linear inequality systems ($Ax \le Bx$).
- Internally, as tropical linear combinations of extreme rays and vertices.
Switching from an external description to an internal one is critical for software static analysis (automatically finding invariants involving $\min$ and $\max$), discrete event systems, and solving mean payoff games. However, previous algorithms suffered from combinatorial explosion: when iteratively adding constraints, the number of candidate generators squared at each step, and filtering out non-extreme candidates required expensive tropical linear-algebraic checks (residuation).
Methods
The paper develops Algorithm $\text{ComputeExtreme}$, which computes intermediate generating sets by eliminating inequalities one by one:
- Candidate Generation: Given an intermediate cone $K$ generated by $G$ and a new halfspace $H = \{x \mid ax \le bx\}$, valid generators are kept, invalid ones are discarded, and cross-combinations $(ah)g \oplus (bg)h$ between satisfying ($g$) and violating ($h$) generators are created as new candidate rays.
- Extremality via Tangent Cones: Rather than comparing a new candidate $g$ against all existing rays in the set, the authors examine the local neighborhood of $g$ via its tangent cone $T(g, C)$. They prove that $g$ is extreme in the polyhedron if and only if the vector $\mathbf{1} = (1, \dots, 1)$ is extreme in $T(g, C)$.
- Directed Hypergraph Reduction: The extremality condition on $T(g, C)$ is equivalent to propagating coordinate zeros. The authors model this as reachability on a directed hypergraph $\mathcal{H}(g, C)$, where nodes represent coordinate indices and hyperedges correspond to the arguments where active constraints achieve equality.
- Almost-Linear Filtering: Candidate extremality holds if and only if the partially ordered strongly connected components (SCCs) of $\mathcal{H}(g, C)$ have a unique least element. Minimal SCCs are computed in $O(\text{size}(\mathcal{H}) \cdot \alpha(d))$ time, where $\alpha$ is the inverse Ackermann function.
- Dynamic Constraint Ordering: Inequalities are dynamically selected at each step to minimize the number of candidate combinations produced.
Datasets
The authors evaluated their OCaml implementation (part of the open-source TPLib library) across three benchmark suites:
- Random Cones (
rndX): Synthetic test sets drawn from uniform random inequalities across dimensions $d \in [12, 25]$ and constraints $n \in [5, 18]$. - Signed Cyclic Cones: Structured instances (up to dimension 35) known to produce theoretically maximal numbers of tropical extreme rays.
- Static Analysis Programs (
oddeven): Real-world verification benchmarks tracking $\min$/$\max$ bounds in odd-even sorting programs of 8 to 10 elements (up to 21 variables and 240 lines of code).
Key Insights and Ideas
- Extremality is purely local: Similar to how Euclidean vertices are certified by full-rank gradients of active constraints, tropical extreme rays are characterized by the subdifferentials of active inequalities at that point.
- Hypergraph connectivity replaces linear rank: In classical geometry, extremality checks involve matrix rank; in tropical geometry, the zero-propagation mechanics of max-plus algebra map directly to tail-to-head hypergraph reachability.
- Decoupling checks from pool size: Prior pruning methods tested candidates against the entire set of accumulated generators $G$, costing $O(d |G|^2)$ per candidate. The hypergraph test relies only on the system of inequalities and dimension $d$, taking $O(n d \alpha(d))$—a vital property when $|G|$ grows exponentially.
Key Results
- Complexity: The elementary pruning step scales as $O(n d \alpha(d) |G|^2)$, compared to $O(n |G|^3)$ in Fukuda and Prodon’s refined classical double description method. The total worst-case execution time is bounded by $O(n^2 d \alpha(d)(n + d)^{d-1})$.
- Empirical Speedups:
- For cyclic cones in dimension 20 with 8 constraints, runtime dropped from 45 days (using previous residuation-based methods) to 690 seconds ($T/T' \approx 1.8 \cdot 10^{-4}$).
- For
cyclic 25, execution dropped from 8 days to 62.6 seconds. - Handled previously intractable instances with tens of thousands of extreme rays, such as
rnd10($d=25, n=10$, yielding 32,699 rays in ~3,000s) andcyclic 35(155,040 rays in 1,232s). - In static analysis benchmarks (
oddeven9), analysis time decreased from over 6 hours (22,101s) to 128 seconds.
Limitations and Future Work
- Worst-Case Exponential Scaling: Because tropical polyhedra can inherently have an exponential number of extreme rays, running time remains bounded by the output size.
- Tightness of Bounds: The worst-case upper bound $O((n+d)^{\lfloor(d-1)/2\rfloor})$ is tight as $d \to \infty$ for fixed $n$, but is known to be loose for fixed $d$ as $n \to \infty$; determining the optimal bound for large $n$ remains open.
- Theoretical vs. Practical Trade-offs: An alternative method based on arrangements of tropical hyperplanes has a slightly better theoretical worst-case bound when $n \gg d$, but always hits its worst case in practice, making the double description method superior for actual computation.
Summary updated