Computing the Extreme Points of Tropical Polyhedra
Xavier Allamigeon, Stéphane Gaubert, Éric Goubault · arXiv (Cornell University) · 2009
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.