The Tropical Double Description Method

Xavier Allamigeon, Stéphane Gaubert, Eric Goubault

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:

  1. Externally, as the solution set of linear inequality systems ($Ax \le Bx$).
  2. 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) and cyclic 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

Abstract

We develop a tropical analogue of the classical double description method allowing one to compute an internal representation (in terms of vertices) of a polyhedron defined externally (by inequalities). The heart of the tropical algorithm is a characterization of the extreme points of a polyhedron in terms of a system of constraints which define it. We show that checking the extremality of a point reduces to checking whether there is only one minimal strongly connected component in an hypergraph. The latter problem can be solved in almost linear time, which allows us to eliminate quickly redundant generators. We report extensive tests (including benchmarks from an application to static analysis) showing that the method outperforms experimentally the previous ones by orders of magnitude. The present tools also lead to worst case bounds which improve the ones provided by previous methods.
BibTeX
@inproceedings{allamigeon2010tropical,
  author = {Xavier Allamigeon and Stéphane Gaubert and Eric Goubault},
  title = {{The Tropical Double Description Method}},
  booktitle = {STACS},
  year = {2010},
  url = {https://openreview.net/forum?id=g6ASZ57zt3},
}

Loading related content...

Figure