Computing the Extreme Points of Tropical Polyhedra

Authors:
  • XAXavier Allamigeon
    Xavier Allamigeon
  • SGStephane Gaubert
    Stephane Gaubert
  • EGEric Goubault
    Eric Goubault
Preprint
Publisher website
Google Scholar
Abstract
We present an efficient algorithm to compute all the extreme elements of a max-plus or tropical polyhedron. This algorithm relies on a combinatorial characterization of these extreme elements, when the polyhedron is defined by inequalities. We show that checking the extremality of an element of such a polyhedron reduces to computing the least model of a compact Horn formula, the latter being a factorized representation of a Horn formula. This allows us to develop an analogue of Motzkin's double description method in which redundant generators are eliminated a priori. We give theoretical bounds and experimental results showing that the algorithm outperforms the previous ones.