×

Computing convex hulls and counting integer points with polymake. (English) Zbl 1370.90009

This paper presents the state of the art of computing integer hulls and their facets as well as counting lattice points in convex polytopes, by making use of the polymake system that allows exploring and testing different algorithmical methods and implementations from the literature. These observations are summarized in ten “rules of thumb”. After the introduction, the reader is familiarized with the polymake system (which provides a common interface for employing and comparing various algorithms and is available from polymake.org). Then, in the third section, various convex hull algorithms and their implementations are implemented and investigated in the polymake system, while Section 4 is devoted to enumerating lattice points in polytopes. Two appendices on the experimental setup and on the computational details close the paper.

MSC:

90-08 Computational methods for problems pertaining to operations research and mathematical programming
52-04 Software, source code, etc. for problems pertaining to convex and discrete geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 4ti2 team, 4ti2—A software package for algebraic, geometric and combinatorial problems on linear spaces. http://www.4ti2.de (2015)
[2] Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1-41. http://mpc.zib.de/index.php/MPC/article/view/4 (2009) · Zbl 1171.90476
[3] Avis, D.: lrslib, version 6.0, http://cgm.cs.mcgill.ca/ avis/C/lrs.html (2015)
[4] Avis, D., Bremner, D. and Seidel, R.: How good are convex hull algorithms? Comput. Geom. 7(5-6), 265-301 (1997) (11th ACM Symposium on Computational Geometry (Vancouver, BC, 1995)) · Zbl 0877.68119
[5] Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom. 8(3), 295-313 (1992) (ACM Symposium on Computational Geometry (North Conway, NH, 1991)) · Zbl 0752.68082
[6] Avis, D., Fukuda, K.: Reverse search for enumeration, Discrete Appl. Math. 65(1-3), 21-46 (1996) (First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz)) · Zbl 0854.68070
[7] Avis, D., Imai, H., Ito, T.: Generating facets for the cut polytope of a graph by triangular elimination. Math. Program. Ser. A 112(2), 303-325 (2008) · Zbl 1190.90281
[8] Avis, D., Jordan, C.: Comparative computational results for some vertex and facet enumeration codes, preprint arXiv:1510.02545 (2015)
[9] Bagnara, R., Hill, P. M., Zaffanella, E.: The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Sci. Comp. Program. 72(1-2), 3-21 (2008)
[10] Baldoni, V., Berline, N., De Loera, J., Dutra, B., Koeppe, M., Vergne, M.: Coefficients of Sylvester’s denumerant, Integers 15, Paper No. A11 (2015) · Zbl 1318.05004
[11] Barahona, F.: The max-cut problem on graphs not contractible to \[K_s\] Ks. Oper. Res. Lett. 2(3), 107-111 (1983) · Zbl 0525.90094
[12] Barvinok, A. I.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19(4), 769-779 (1994) · Zbl 0821.90085
[13] Behle, M.: On threshold BDDs and the optimal variable ordering problem, Combinatorial Optimization and Applications. In: Andreas, D., Yinfeng, X., Binhai, Z. (eds) Lecture Notes in Computer Science, vol. 4616, pp. 124-135, Springer Berlin Heidelberg (English) (2007) · Zbl 1175.90324
[14] Bejraburnin, N.: On facet inequalities of correlation polytopes, http://math.berkeley.edu/ natth/files/STAT241A.pdf
[15] Karl, H.B.: Average-case analysis of the double description method and the beneath-beyond algorithm. Discrete Comput. Geom. 37(2), 175-204 (2007) · Zbl 1115.68155
[16] Bremner, D.: Incremental convex hull algorithms are not output sensitive. Discrete Comput. Geom. 21(1), 57-68 (1999) · Zbl 0924.68192
[17] Bremner, D., Dutour Sikirić, M., Schürmann, A.: Polyhedral representation conversion up to symmetries. Polyhedral computation, CRM Proc. Lecture Notes, vol. 48, Amer. Math. Soc., Providence, RI, pp. 45-71 (2009) · Zbl 1170.68621
[18] Bruns, W., Ichim, B., Söger, C.: The power of pyramid decomposition in Normaliz, J. Symbolic Comput. 74, 513-536 (2016) · Zbl 1332.68298
[19] Bruns, W., Ichim, B., Söger, C., Römer, T.: Normaliz. Algorithms for rational cones and affine monoids, version 2.99.4, http://www.math.uos.de/normaliz (2015)
[20] Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom. 10(4), 377-409 (1993) · Zbl 0786.68091
[21] Chernikova, N.V.: Algorithm for finding a general formula for the non-negative solutions of system of linear equations. USSR Comput. Math. Math. Phys. 4(4), 151-158 (1964) · Zbl 0221.65055
[22] Christof, T.: SMAPO, a library of linear descriptions of low-dimensional 0/1-polytopes connected with small instances of combinatorial optimization problems. http://www.iwr.uni-heidelberg.de/groups/comopt/software/SMAPO/cut/cut.html (2010)
[23] Christof, T., Loebel, A.: PORTA, version 1.4.1-20090921. http://porta.zib.de/ (2009)
[24] IBM Corporation, ILOG CPLEX, http://www.ibm.com/software/commerce/optimization/cplex-optimizer/ · Zbl 1115.68155
[25] De Loera, J.A.: The many aspects of counting lattice points in polytopes. Math. Semesterber. 52(2), 175-195 (2005) · Zbl 1093.52006
[26] De Loera, J.A., Berline, N., Baldoni, V., Dutra, B., Köppe, M., Moreinis, S., Pinto, G., Vergne, M., Wu, J.: A user’s guide for LattE integrale v1.7.3, software package LattE is available at http://www.math.ucdavis.edu/ latte/, (2015) · Zbl 1115.68155
[27] De Loera, J. A., Dutra, B., Köppe, M., Moreinis, S., Pinto, G., Wu, J.: Software for exact integration of polynomials over polyhedra. Comput. Geom. 46(3), 232-252 (2013) · Zbl 1259.65054
[28] Dewey, C., Woods, K.: Parametric Sequence Alignment, Algebraic Statistics for Computational Biology. Cambridge Univ. Press, New York (2005) · Zbl 1374.92111
[29] Edelsbrunner, H.: Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10. Springer-Verlag, Berlin (1987) · Zbl 0634.52001
[30] Koch, T. et al.: MIPLIB 2010. Math. Program. Comput. 3(2) 103-163 (english), http://miplib.zib.de/miplib2010.php (2011)
[31] Granlund, T. et al.: GNU multiple precision arithmetic library 5.1.2, http://gmplib.org/
[32] Fukuda, K.: cddlib, version 0.94h, http://www.inf.ethz.ch/personal/fukudak/cdd_home/ (2015)
[33] Fukuda, K., Prodon, A.: Double description method revisited, Combinatorics and computer science (Brest 1995), Lecture Notes in Comput. Sci., vol. 1120, pp 91-111, Springer, Berlin (1996)
[34] Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979) · Zbl 0411.68039
[35] Gawrilow, E., Joswig, M.: Polymake: a framework for analyzing convex polytopes, Polytopes-combinatorics and computation (Oberwolfach 1997), DMV Sem., vol. 29, pp. 43-73, Birkhäuser, Basel, (2000) · Zbl 0960.68182
[36] Gawrilow, E., Joswig, M.: Flexible object hierarchies in polymake. In: Andrés, I., Nobuki, T. (eds.) Proceedings of the 2nd International Congress of Mathematical Software, 1-3. September 2006, pp. 219-221, Castro Urdiales, Spanien (2006) · Zbl 1230.52003
[37] Ghemawat, S., Menage, P.: Thread-Caching Malloc part of the Google Performance Tools. http://goog-perftools.sourceforge.net/doc/tcmalloc.html
[38] Gurobi Optimization, Inc., Gurobi optimizer reference manual (2013)
[39] Hayes, A.C., David, G., Larman, : The vertices of the knapsack polytope. Discrete Appl. Math. 6(2), 135-138 (1983) · Zbl 0523.90063
[40] Hemmecke, R.: On the computation of Hilbert bases of cones, Mathematical software (Beijing, 2002) World Sci. Publ. River Edge, NJ 2002, pp. 307-317 · Zbl 1191.11037
[41] The MathWorks Inc., MATLAB version 8.2.0.701 (r2013b), http://mathworks.com, Natick, Massachusetts (2010)
[42] Joswig, M.: Beneath-and-Beyond Revisited, Algebra, Geometry, and Software Systems. Springer, Berlin (2003) · Zbl 1027.68128
[43] Joswig, M., Loho, G., Lorenz, B., Schröter, B.: Linear programs and convex hulls over fields of Puiseux fractions. In: Mathematical Aspects of Computer and Information Sciences: 6th International Conference, MACIS 2015, Berlin, Germany, November 11-13, 2015, Revised Selected Papers, Lecture Notes in Comput. Sci., vol. 9582, pp 429-445, Springer, Berlin (2016) · Zbl 1460.90106
[44] Joswig, M., Theobald, T.: Polyhedral and algebraic methods in computational geometry, Universitext, Springer, London, 2013, Revised and updated translation of the 2008 German original · Zbl 1267.52001
[45] Joswig, M., Ziegler, G. M.: Convex hulls, oracles, and homology. J. Symbolic Comput. 38(4), 1247-1259 (2004) · Zbl 1121.52030
[46] Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V.: Generating all vertices of a polyhedron is hard. Discrete Comput. Geom. 39(1-3), 174-190 (2008) · Zbl 1147.05040
[47] Klee, V., Minty, G.J.: How good is the simplex algorithm? Inequalities III. In: Proceedings of Third Symposium University California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin, pp. 159-175, Academic Press, New York (1972)
[48] Koeppe, M., Verdoolaege, S., Woods, K.: An implementation of the Barvinok-Woods integer projection algorithm. In: Proceedings of the International Conference on Information Theory and Statistical Learning, pp. 53-59 (2008)
[49] Köppe, M.: A primal Barvinok algorithm based on irrational decompositions. SIAM J. Discrete Math. 21(1), 220-236 (electronic) (2007) · Zbl 1135.05003
[50] McMullen, P.: The numbers of faces of simplicial polytopes. Israel J. Math. 9, 559-570 (1971) · Zbl 0209.53701
[51] Motzkin, T.S., Raiffa, H., Thompson, G.L., Thrall, R.M.: The double description method, Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, pp. 51-73, Princeton University Press, Princeton, (1953) · Zbl 0050.14201
[52] Murai, S., Nevo, E.: On the generalized lower bound conjecture for polytopes and spheres. Acta Math. 210(1), 185-202 (2013) · Zbl 1279.52014
[53] Opfer, T.: Entwicklung eines exakten rationalen dualen Simplex-Lösers, Master’s thesis, TU Darmstadt, (2011)
[54] The polymake team, Computing convex hulls and counting integer points with polymake, http://www.polymake.org/doku.php/researchdata/polymakeilp, Experimental data and source code (2015)
[55] The polymake team, polymake, version 2.14, http://www.polymake.org (2015)
[56] Loïc, P.: The Euclidean algorithm in dimension \[n\] n, ISSAC ’96. Proceedings of the 1996 international symposium on Symbolic and algebraic computation, pp. 40-42 (1996) · Zbl 0919.11088
[57] Rehn, T.: Polyhedral description conversion up to symmetries, Master’s thesis, Otto-von-Guericke-Universität Magdeburg, (2010)
[58] Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency. Vol. C, Algorithms and Combinatorics, vol. 24, pp. 70-83, Springer-Verlag, Berlin, Disjoint paths, hypergraphs, Chapters (2003)
[59] Seidel, R.: A convex hull algorithm optimal for point sets in even dimensions. Tech. report, University of British Columbia, Department of Computer Science (1981)
[60] Tantau, T.: TikZ ist kein Zeichenprogramm PGF/TikZ, http://www.ctan.org/tex-archive/graphics/pgf/
[61] The CGAL Project, CGAL user and reference manual, 4.7 ed., CGAL Editorial Board, (2015)
[62] Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410-421 (1979) · Zbl 0419.68082
[63] Verdoolaege, S.: barvinok, http://barvinok.gforge.inria.fr/ · Zbl 1180.52014
[64] Walter, M.: Unimodularity-test extension for polymake, https://github.com/xammy/unimodularity-test
[65] Walter, M., Truemper, K.: Implementation of a unimodularity test. Math. Program. Comput. 5(1), 57-73 (2013) · Zbl 1262.05020
[66] Ziegler, G.M.: Lectures on polytopes, Graduate Texts in Mathematics, vol. 152. Springer-Verlag, New York (1995) · Zbl 0823.52002
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.