The tropical double description method

Xavier Allamigeon, Stéphane Gaubert, Eric Goubault

TL;DR

This paper introduces a new algorithm, the "tropical double description method," for efficiently computing the internal representation (extreme points and rays) of tropical polyhedra, which are analogues of convex polyhedra in tropical algebra. This method significantly outperforms existing approaches, achieving speedups of orders of magnitude, and has direct applications in areas like static program analysis and control theory.

What Problem Does This Paper Address?

In mathematics and computer science, polyhedra (geometric shapes defined by linear inequalities) are fundamental. A common task is to represent these polyhedra internally, typically by listing their extreme points and rays, given an external description (the inequalities). This paper tackles the tropical analogue of this problem. Tropical algebra, often using the "max-plus" semiring, has emerged as a powerful tool for modeling systems with discrete events, optimization problems, and even program analysis. However, efficiently computing the internal representation of tropical polyhedra has been a significant bottleneck. Existing methods for this task are computationally expensive, often involving operations that grow quadratically or worse with the number of generators, making them impractical for larger problems.

Methods

The core contribution is a tropical analogue of the "double description method," a classical algorithm for computing polyhedron representations. The key innovation lies in a novel characterization of "extremality" for points in a tropical polyhedron. Instead of relying on traditional geometric notions, the authors translate the problem into a combinatorial one involving directed hypergraphs. Specifically, they show that checking if a point is an extreme generator of a tropical polyhedron reduces to analyzing the strongly connected components (SCCs) of an associated hypergraph. This hypergraph analysis can be performed efficiently, in almost linear time. The algorithm iteratively refines the set of generators by considering one inequality at a time, using a theorem that describes how to update the generator set when intersecting a cone with a tropical halfspace. Redundant generators are then pruned using the new hypergraph-based extremality test.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and theoretical analysis, with experimental validation on generated "random" cones and specific benchmark cases from static analysis applications.

Key Insights and Ideas

  • Bridging Tropical Algebra and Computational Geometry: The paper successfully translates a fundamental problem in computational geometry (double description) into the realm of tropical algebra, opening new avenues for algorithmic development.
  • Hypergraph-based Extremality: The most significant insight is the reduction of tropical polyhedron extremality to a problem on directed hypergraphs, specifically the analysis of their strongly connected components. This provides a computationally efficient way to prune redundant generators.
  • Local Property of Extremality: The paper demonstrates that extremality in tropical polyhedra is a local property, which can be analyzed using the "tangent cone" around a point.
  • Efficiency Gains: The new method offers a substantial performance improvement over existing algorithms, making previously intractable problems solvable.

Key Results

  • New Algorithm: The paper presents the "tropical double description method," an algorithm for computing the extreme generators of tropical polyhedra.
  • Efficiency: Experimental results show that the proposed algorithm outperforms previous methods by "orders of magnitude." For instance, problems that took days for older algorithms can be solved in seconds or minutes.
  • Improved Worst-Case Bounds: The new approach also leads to better theoretical worst-case complexity bounds for computing tropical polyhedra representations compared to existing methods.
  • Applications: The method has been successfully applied to static program analysis, demonstrating its practical relevance.

Limitations and Future Work

  • Worst-Case vs. Average-Case: While the algorithm shows excellent practical performance, the paper notes that the number of generators can still be exponential in the dimension in the worst case (as per Theorem 4.2). The practical efficiency often stems from the fact that the actual number of generators is much smaller than this theoretical upper bound.
  • Open Problems: The paper mentions that finding the optimal worst-case bound for the number of extreme rays of a tropical cone is an open problem.
  • Future Work: The authors suggest that their tools can lead to improved worst-case bounds for other problems and that the method's efficiency is crucial for scaling up applications in static analysis and discrete event systems. Further exploration of the connection between tropical polyhedra and other areas like mean payoff games is also implied.

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},
}
Figure