×

Computing the vertices of tropical polyhedra using directed hypergraphs. (English) Zbl 1312.52001

Summary: We establish a characterization of the vertices of a tropical polyhedron defined as the intersection of finitely many half-spaces. We show that a point is a vertex if, and only if, a directed hypergraph, constructed from the subdifferentials of the active constraints at this point, admits a unique strongly connected component that is maximal with respect to the reachability relation (all the other strongly connected components have access to it). This property can be checked in almost linear-time. This allows us to develop a tropical analogue of the classical double description method, which computes a minimal internal representation (in terms of vertices) of a polyhedron defined externally (by half-spaces or hyperplanes). We provide theoretical worst case complexity bounds and report extensive experimental tests performed using the library TPLib, showing that this method outperforms the other existing approaches.

MSC:

52A01 Axiomatic and generalized convexity
05C65 Hypergraphs
14T05 Tropical geometry (MSC2010)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

Maxplus; polymake; TPLib
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ardila, F., Develin, M.: Tropical hyperplane arrangements and oriented matroids. Math. Z. 262, 795-816 (2009) · Zbl 1175.52024 · doi:10.1007/s00209-008-0400-z
[2] Allamigeon, X., Gaubert, S., Goubault, É.: Inferring min and max invariants using max-plus polyhedra, SAS’08. Lecture Notes in Computer Science, vol. 5079, pp. 189-204. Springer, Valencia (2008) · Zbl 1149.68346
[3] Akian, M., Gaubert, S., Guterman, A.: Tropical linear independence and beyond. In: Litvinov, G.L., Sergeev, S.N. (eds.) Proceedings of the International Conference on Tropical and Idempotent Mathematics. Contemporary Mathematics, vol. 495, pp. 1-38. American Mathematical Society, Providence (2009) · Zbl 1182.15002
[4] Allamigeon, X., Gaubert, S., Goubault, E.: The tropical double description method. In: Marion, J.-Y., Schwentick, Th. (eds.) Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), Dagstuhl, Germany. Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, pp. 47-58. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2010) · Zbl 1230.52024
[5] Akian, M., Gaubert, S., Kolokoltsov, V.N.: Set coverings and invertibility of functional galois connections. In: Litvinov, G.L., Maslov, V.P. (eds.) Idempotent Mathematics and Mathematical Physics. Contemporary Mathematics, pp. 19-51. American Mathematical Society, Providence (2005) · Zbl 1080.06001
[6] Akian, M., Gaubert, S., Guterman, A.: Tropical polyhedra are equivalent to mean payoff games. Int. J. Algebra Comput. 22(1), 125001 (2012). doi:10.1142/s0218/96711006674 · Zbl 1239.14054
[7] Allamigeon, X.: Static analysis of memory manipulations by abstract interpretation—algorithmics of tropical polyhedra, and application to abstract interpretation. Ph.D. thesis, École Polytechnique, Palaiseau, France, November 2009. http://www.cmap.polytechnique.fr/allamigeon/papers/thesis.pdf
[8] Allamigeon, X.: Strongly connected components of directed hypergraphs, arXiv:cs.DS/1112.1444 (2011) · Zbl 1360.68485
[9] Allamigeon, X.: TPLib: tropical polyhedra library in OCaml. https://gforge.inria.fr/projects/tplib (2011)
[10] Allamigeon, X., Gaubert, S., Katz, R.D.: Tropical polar cones, hypergraph transversals, and mean payoff games. Linear Algebr. Appl. 435(7), 1549-1574 (2011) (Special Issue dedicated to 1st Montreal Workshop) · Zbl 1217.14047
[11] Allamigeon, X., Gaubert, S., Katz, R.D.: The number of extreme points of tropical polyhedra. J. Combin. Theory A 118(1), 162-189 (2011) · Zbl 1246.14078 · doi:10.1016/j.jcta.2010.04.003
[12] Butkovič, P., Hegedüs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonomicko-matematicky Obzor. 20, 203-215 (1984) · Zbl 0545.90101
[13] Briec, W., Horvath, \[C.: \mathbb{B} \]-convexity. Optimization 53, 103-127 (2004) · Zbl 1144.90506 · doi:10.1080/02331930410001695283
[14] Briec, W., Horvath, C.: A B-convex production model for evaluating performance of firms. J. Math. Anal. Appl. 355(1), 131-144 (2009) · Zbl 1204.90031 · doi:10.1016/j.jmaa.2009.01.048
[15] Bezem, M., Nieuwenhuis, R., Rodríguez-Carbonell, E.: Hard problems in max-algebra, control theory, hypergraphs and other areas. Inf. Process. Lett. 110, 133-138 (2010) · Zbl 1206.68284 · doi:10.1016/j.ipl.2009.11.007
[16] Butkovič, P.: Max-algebra: the linear algebra of combinatorics? Linear Algebr. Appl. 367, 313-335 (2003) · Zbl 1022.15017 · doi:10.1016/S0024-3795(02)00655-9
[17] Butkovič, P.: Systems, max-linear: theory and algorithms. Springer Monographs in Mathematics. Springer, Berlin (2010) · Zbl 1202.15032 · doi:10.1007/978-1-84996-299-5
[18] Butkovič, P., Schneider, H., Sergeev, S.: Generators, extremals and bases of max cones. Linear Algebr. Appl. 421(2-3), 394-406 (2007) · Zbl 1119.15018 · doi:10.1016/j.laa.2006.10.004
[19] Block, F., Yu, J.: Tropical convexity via cellular resolutions. J. Algebr. Combin. 24(1), 103-114 (2006) · Zbl 1097.52506 · doi:10.1007/s10801-006-9104-9
[20] Cuninghame-Green, R.A.: Minimax Algebra. Lecture Notes in Economics and Mathematical Systems, vol. 166. Springer, Berlin (1979) · Zbl 0399.90052
[21] Cohen, G., Gaubert, S., McGettrick, M., Quadrat, J.-P.: Maxplus toolbox of scilab, 1998. http://minimal.inria.fr/gaubert/maxplustoolbox; now integrated in ScicosLab
[22] Cohen, G., Gaubert, S., Quadrat, J.P.: Max-plus algebra and system theory: where we are and where to go now. Ann. Rev. Control 23, 207-219 (1999)
[23] Cohen, G.; Gaubert, S.; Quadrat, JP; Menaldi, JL (ed.); Rofman, E. (ed.); Sulem, A. (ed.), Hahn-Banach separation theorem for max-plus semimodules, 325-334 (2001), Amsterdam · Zbl 1054.46500
[24] Cohen, G., Gaubert, S., Quadrat, J.P.: Duality and separation theorem in idempotent semimodules. Linear Algebr. Appl. 379, 395-422 (2004) · Zbl 1042.46004 · doi:10.1016/j.laa.2003.08.010
[25] Cohen, G., Gaubert, S., Quadrat, J.P., Singer, I.: Max-plus convex sets and functions. In: Litvinov, G.L., Maslov, V.P. (eds.) Idempotent Mathematics and Mathematical Physics. Contemporary Mathematics, pp. 105-129. American Mathematical Society, Providence (2005) · Zbl 1093.26005
[26] Di Loreto, M., Gaubert, S., Katz, R.D., Loiseau, J.-J.: Duality between invariant spaces for max-plus linear discrete event systems. SIAM J. Control Optim. 48(8), 5606-5628 (2010) · Zbl 1213.93128 · doi:10.1137/090747191
[27] Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9, 1-27 (2004) · Zbl 1054.52004
[28] Develin, M. Santos, F., Sturmfels, B.: On the rank of a tropical matrix. In: Combinatorial and Computational Geometry, Mathematical Sciences Research Institute (MSRI), Publication, vol. 52, pp. 213-242. Cambridge University Press, Cambridge (2005) · Zbl 1095.15001
[29] Develin, M., Yu, J.: Tropical polytopes and cellular resolutions. Exp. Math. 16(3), 277-292 (2007) · Zbl 1134.52006 · doi:10.1080/10586458.2007.10129009
[30] Einsiedler, M., Kapranov, M., Lind, D.: Non-Archimedean amoebas and tropical varieties. J. Reine Angew. Math. 601, 139-157 (2006) · Zbl 1115.14051
[31] Fukuda, K., Prodon, A.: Double description method revisited. Selected Papers from the 8th Franco-Japanese and 4th Franco-Chinese Conference on Combinatorics and Computer Science (London, UK). pp. 91-111. Springer, Berlin (1996)
[32] Gaubert, S.: Théorie des systèmes linéaires dans les dioïdes. Thèse, École des Mines de Paris, July (1992)
[33] Gaubert, S., Katz, R.D.: Max-plus convex geometry. In: Schmidt, R.A. (ed.) RelMiCS/AKA. Lecture Notes in Computer Science, vol. 4136, pp. 192-206. Springer, Berlin (2006) · Zbl 1134.52303
[34] Gaubert, S., Katz, R.D.: The Minkowski theorem for max-plus convex sets. Linear Algebr. Appl. 421, 356-369 (2007) · Zbl 1110.52002 · doi:10.1016/j.laa.2006.09.019
[35] Gaubert, S., Katz, R.D.: Minimal half-spaces and external representation of tropical polyhedra. J. Algebr. Combin. 33(3), 325-348 (2011) · Zbl 1218.52001 · doi:10.1007/s10801-010-0246-4
[36] Gaubert, S., Meunier, F.: Carathodory, Helly and the others in the max-plus world. Discrete Comput. Geom. 43, 648-662 (2010) · Zbl 1219.14071 · doi:10.1007/s00454-009-9207-x
[37] Gaubert, S., Plus, M.: Methods and applications of (max,+) linear algebra. In: Reischuk, R., Morvan, M. (eds.) STACS’97 (Lübeck). Lecture Notes in Computer Science, vol. 1200. Springer, Berlin (1997) · Zbl 1498.15034
[38] Gaubert, S., Sergeev, S.: Cyclic projectors and separation theorems in idempotent convex geometry. Fundam. Prikl. Math. 13(4), 33-52 (2007)
[39] Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discret. Appl. Math. 42(2-3), 177-201 (1993) · Zbl 0771.05074 · doi:10.1016/0166-218X(93)90045-P
[40] Gawrilow, E.; Joswig, M.; Kalai, G. (ed.); Ziegler, GM (ed.), Polymake: a framework for analyzing convex polytopes, 43-74 (2000), Basel · Zbl 0960.68182
[41] Joswig, M.: Tropical halfspaces. Combinatorial and Computational Geometry. Mathematical Sciences Research Institute Publications, vol. 52, pp. 409-431. Cambridge University Press, Cambridge (2005) · Zbl 1090.52500
[42] Joswig, M.: Tropical Convex Hull Computations. American Mathematical Society, Providence (2009) · Zbl 1202.52004
[43] Joswig, M., Sturmfels, B., Yu, J.: Affine buildings and tropical convexity. Albanian J. Math. 1(4), 187-211 (2007) · Zbl 1133.52003
[44] Katz, R.D.: Max-plus \[(A, B)\]-invariant spaces and control of timed discrete event systems. IEEE Trans. Autom. Control 52(2), 229-241 (2007) · Zbl 1366.93351 · doi:10.1109/TAC.2006.890478
[45] Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM 22(4), 469-476 (1975) · Zbl 0316.68030 · doi:10.1145/321906.321910
[46] Lorenzo, E., de la Puente, M.J.: An algorithm to describe the solution set of any tropical linear system \[A \odot x = B \odot x\]. Linear Algebr. Appl. 435(4), 884-901 (2011) · Zbl 1217.65076 · doi:10.1016/j.laa.2011.02.014
[47] Litvinov, G.L., Maslov, V.P., Shpiz, G.B.: Idempotent functional analysis: an algebraic approach. Math. Notes 69(5), 696-729 (2001) · Zbl 1017.46034 · doi:10.1023/A:1010266012029
[48] McMullen, P.: The maximum numbers of faces of a convex polytope. Mathematika 17, 179-184 (1970) · Zbl 0217.46703 · doi:10.1112/S0025579300002850
[49] Motzkin, TS; Raiffa, H.; Thompson, GL; Thrall, RM; Kuhn, HW (ed.); Tucker, AW (ed.), The double description method, No. II, 51-73 (1953), Princeton · Zbl 0050.14201
[50] Maslov, V., Samborskiĭ, S. (eds.), Idempotent analysis. Advances in Soviet Mathematics, vol. 13. American Mathematical Society, Providence (1992) · Zbl 0772.00015
[51] Nitica, V., Singer, I.: Max-plus convex sets and max-plus semispaces. I. Optimization 56(1-2), 171-205 (2007) · Zbl 1121.52002 · doi:10.1080/02331930600819852
[52] Plus, M.: Linear systems in \[(\max ,+)\]-algebra. In: Proceedings of the 29th Conference on Decision and Control (Honolulu), December 1990 · Zbl 0699.90094
[53] Richter-Gebert, J., Sturmfels, B., Theobald, T.: First steps in tropical geometry. In: Idempotent Mathematics and Mathematical Physics. Contemporary Mathematics, vol. 377, pp. 289-317. American Mathematical Society, Providence (2005) · Zbl 1093.14080
[54] Singer, I.: Abstract Convex Analysis. Wiley, New York (1997) · Zbl 0898.49001
[55] Speyer, D., Sturmfels, B.: The tropical Grassmannian. Adv. Geom. 4(3), 389-411 (2004) · Zbl 1065.14071 · doi:10.1515/advg.2004.023
[56] Truffet, L.: A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spaces. Beiträge Algebr. Geom. 51(2), 313-336 (2010) · Zbl 1342.52026
[57] Tarjan, R.E., van Leeuwen, J.: Worst-case analysis of set union algorithms. J. ACM 31(2), 245-281 (1984) · Zbl 0632.68043 · doi:10.1145/62.2160
[58] Vorobyev, N.N.: Extremal algebra of positive matrices. Elektron. Informationsverarbeitung Kybern. 3, 39-71 (1967) (in Russian)
[59] Ziegler, G.M.: Lectures on Polytopes, 2nd edn. Springer, New York (1998)
[60] Zimmermann, K.: Extremální algebra. Ekonomický ùstav ùSAV, Praha (1976) (in Czech)
[61] Zimmermann, K.: A general separation theorem in extremal algebras. Ekonom. Mat. Obzor. 13(2), 179-201 (1977) · Zbl 0365.90127
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.