{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T00:51:28Z","timestamp":1778201488644,"version":"3.51.4"},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,5,23]],"date-time":"2016-05-23T00:00:00Z","timestamp":1463961600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s12532-016-0104-z","type":"journal-article","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T05:35:40Z","timestamp":1464068140000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":65,"title":["Computing convex hulls and counting integer points with polymake"],"prefix":"10.1007","volume":"9","author":[{"given":"Benjamin","family":"Assarf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ewgenij","family":"Gawrilow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katrin","family":"Herr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Joswig","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Lorenz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Paffenholz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Rehn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,23]]},"reference":[{"key":"104_CR1","unstructured":"4ti2 team, 4ti2\u2014A software package for algebraic, geometric and combinatorial problems on linear spaces. http:\/\/www.4ti2.de (2015)"},{"key":"104_CR2","doi-asserted-by":"crossref","unstructured":"Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1\u201341. http:\/\/mpc.zib.de\/index.php\/MPC\/article\/view\/4 (2009)","DOI":"10.1007\/s12532-008-0001-1"},{"key":"104_CR3","unstructured":"Avis, D.: lrslib, version 6.0, http:\/\/cgm.cs.mcgill.ca\/~avis\/C\/lrs.html (2015)"},{"key":"104_CR4","doi-asserted-by":"crossref","unstructured":"Avis, D., Bremner, D. and Seidel, R.: How good are convex hull algorithms? Comput. Geom. 7(5\u20136), 265\u2013301 (1997) (11th ACM Symposium on Computational Geometry (Vancouver, BC, 1995))","DOI":"10.1016\/S0925-7721(96)00023-5"},{"key":"104_CR5","doi-asserted-by":"crossref","unstructured":"Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom. 8(3), 295\u2013313 (1992) (ACM Symposium on Computational Geometry (North Conway, NH, 1991))","DOI":"10.1007\/BF02293050"},{"key":"104_CR6","doi-asserted-by":"crossref","unstructured":"Avis, D., Fukuda, K.: Reverse search for enumeration, Discrete Appl. Math. 65(1\u20133), 21\u201346 (1996) (First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz))","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"104_CR7","doi-asserted-by":"crossref","unstructured":"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\u2013325 (2008)","DOI":"10.1007\/s10107-006-0018-z"},{"key":"104_CR8","unstructured":"Avis, D., Jordan, C.: Comparative computational results for some vertex and facet enumeration codes, preprint arXiv:1510.02545 (2015)"},{"key":"104_CR9","doi-asserted-by":"crossref","unstructured":"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\u20132), 3\u201321 (2008)","DOI":"10.1016\/j.scico.2007.08.001"},{"key":"104_CR10","unstructured":"Baldoni, V., Berline, N., De\u00a0Loera, J., Dutra, B., Koeppe, M., Vergne, M.: Coefficients of Sylvester\u2019s denumerant, Integers 15, Paper No. A11 (2015)"},{"key":"104_CR11","doi-asserted-by":"crossref","unstructured":"Barahona, F.: The max-cut problem on graphs not contractible to $$K_{s}$$ K s . Oper. Res. Lett. 2(3), 107\u2013111 (1983)","DOI":"10.1016\/0167-6377(83)90016-0"},{"key":"104_CR12","doi-asserted-by":"crossref","unstructured":"Barvinok, A. I.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19(4), 769\u2013779 (1994)","DOI":"10.1287\/moor.19.4.769"},{"key":"104_CR13","doi-asserted-by":"crossref","unstructured":"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.\u00a0124\u2013135, Springer Berlin Heidelberg (English) (2007)","DOI":"10.1007\/978-3-540-73556-4_15"},{"key":"104_CR14","unstructured":"Bejraburnin, N.: On facet inequalities of correlation polytopes, http:\/\/math.berkeley.edu\/~natth\/files\/STAT241A.pdf"},{"issue":"2","key":"104_CR15","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/s00454-006-1257-8","volume":"37","author":"HB Karl","year":"2007","unstructured":"Karl, H.B.: Average-case analysis of the double description method and the beneath-beyond algorithm. Discrete Comput. Geom. 37(2), 175\u2013204 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"104_CR16","doi-asserted-by":"crossref","unstructured":"Bremner, D.: Incremental convex hull algorithms are not output sensitive. Discrete Comput. Geom. 21(1), 57\u201368 (1999)","DOI":"10.1007\/PL00009410"},{"key":"104_CR17","doi-asserted-by":"crossref","unstructured":"Bremner, D., Dutour\u00a0Sikiri\u0107, M., Sch\u00fcrmann, A.: Polyhedral representation conversion up to symmetries. Polyhedral computation, CRM Proc. Lecture Notes, vol.\u00a048, Amer. Math. Soc., Providence, RI, pp.\u00a045\u201371 (2009)","DOI":"10.1090\/crmp\/048\/03"},{"key":"104_CR18","doi-asserted-by":"crossref","unstructured":"Bruns, W., Ichim, B., S\u00f6ger, C.: The power of pyramid decomposition in Normaliz, J. Symbolic Comput. 74, 513\u2013536 (2016)","DOI":"10.1016\/j.jsc.2015.09.003"},{"key":"104_CR19","unstructured":"Bruns, W., Ichim, B., S\u00f6ger, C., R\u00f6mer, T.: Normaliz. Algorithms for rational cones and affine monoids, version 2.99.4, http:\/\/www.math.uos.de\/normaliz (2015)"},{"key":"104_CR20","doi-asserted-by":"crossref","unstructured":"Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom. 10(4), 377\u2013409 (1993)","DOI":"10.1007\/BF02573985"},{"issue":"4","key":"104_CR21","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0041-5553(64)90009-6","volume":"4","author":"NV Chernikova","year":"1964","unstructured":"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\u2013158 (1964)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"104_CR22","unstructured":"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)"},{"key":"104_CR23","unstructured":"Christof, T., Loebel, A.: PORTA, version 1.4.1-20090921. http:\/\/porta.zib.de\/ (2009)"},{"key":"104_CR24","unstructured":"IBM Corporation, ILOG CPLEX, http:\/\/www.ibm.com\/software\/commerce\/optimization\/cplex-optimizer\/"},{"key":"104_CR25","doi-asserted-by":"crossref","unstructured":"De Loera, J.A.: The many aspects of counting lattice points in polytopes. Math. Semesterber. 52(2), 175\u2013195 (2005)","DOI":"10.1007\/s00591-005-0094-9"},{"key":"104_CR26","unstructured":"De Loera, J.A., Berline, N., Baldoni, V., Dutra, B., K\u00f6ppe, M., Moreinis, S., Pinto, G., Vergne, M., Wu, J.: A user\u2019s guide for LattE integrale v1.7.3, software package LattE is available at http:\/\/www.math.ucdavis.edu\/~latte\/ , (2015)"},{"key":"104_CR27","doi-asserted-by":"crossref","unstructured":"De Loera, J. A., Dutra, B., K\u00f6ppe, M., Moreinis, S., Pinto, G., Wu, J.: Software for exact integration of polynomials over polyhedra. Comput. Geom. 46(3), 232\u2013252 (2013)","DOI":"10.1016\/j.comgeo.2012.09.001"},{"key":"104_CR28","doi-asserted-by":"crossref","unstructured":"Dewey, C., Woods, K.: Parametric Sequence Alignment, Algebraic Statistics for Computational Biology. Cambridge Univ. Press, New York (2005)","DOI":"10.1017\/CBO9780511610684.011"},{"key":"104_CR29","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H.: Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10. Springer-Verlag, Berlin (1987)","DOI":"10.1007\/978-3-642-61568-9"},{"key":"104_CR30","doi-asserted-by":"crossref","unstructured":"Koch, T. et\u00a0al.: MIPLIB 2010. Math. Program. Comput. 3(2) 103\u2013163 (english), http:\/\/miplib.zib.de\/miplib2010.php (2011)","DOI":"10.1007\/s12532-011-0025-9"},{"key":"104_CR31","unstructured":"Granlund, T. et\u00a0al.: GNU multiple precision arithmetic library 5.1.2, http:\/\/gmplib.org\/"},{"key":"104_CR32","unstructured":"Fukuda, K.: cddlib, version 0.94h, http:\/\/www.inf.ethz.ch\/personal\/fukudak\/cdd_home\/ (2015)"},{"key":"104_CR33","doi-asserted-by":"crossref","unstructured":"Fukuda, K., Prodon, A.: Double description method revisited, Combinatorics and computer science (Brest 1995), Lecture Notes in Comput. Sci., vol. 1120, pp 91\u2013111, Springer, Berlin (1996)","DOI":"10.1007\/3-540-61576-8_77"},{"key":"104_CR34","unstructured":"Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"104_CR35","unstructured":"Gawrilow, E., Joswig, M.: Polymake: a framework for analyzing convex polytopes, Polytopes\u2013combinatorics and computation (Oberwolfach 1997), DMV Sem., vol. 29, pp. 43\u201373, Birkh\u00e4user, Basel, (2000)"},{"key":"104_CR36","doi-asserted-by":"crossref","unstructured":"Gawrilow, E., Joswig, M.: Flexible object hierarchies in polymake. In: Andr\u00e9s, I., Nobuki, T. (eds.) Proceedings of the 2nd International Congress of Mathematical Software, 1\u20133. September 2006, pp.\u00a0219\u2013221, Castro Urdiales, Spanien (2006)","DOI":"10.1007\/11832225_20"},{"key":"104_CR37","unstructured":"Ghemawat, S., Menage, P.: Thread-Caching Malloc part of the Google Performance Tools. http:\/\/goog-perftools.sourceforge.net\/doc\/tcmalloc.html"},{"key":"104_CR38","unstructured":"Gurobi Optimization, Inc., Gurobi optimizer reference manual (2013)"},{"issue":"2","key":"104_CR39","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0166-218X(83)90067-7","volume":"6","author":"AC Hayes","year":"1983","unstructured":"Hayes, A.C., David, G., Larman, : The vertices of the knapsack polytope. Discrete Appl. Math. 6(2), 135\u2013138 (1983)","journal-title":"Discrete Appl. Math."},{"key":"104_CR40","doi-asserted-by":"crossref","unstructured":"Hemmecke, R.: On the computation of Hilbert bases of cones, Mathematical software (Beijing, 2002) World Sci. Publ. River Edge, NJ 2002, pp. 307\u2013317","DOI":"10.1142\/9789812777171_0032"},{"key":"104_CR41","unstructured":"The\u00a0MathWorks Inc., MATLAB version 8.2.0.701 (r2013b), http:\/\/mathworks.com , Natick, Massachusetts (2010)"},{"key":"104_CR42","doi-asserted-by":"crossref","unstructured":"Joswig, M.: Beneath-and-Beyond Revisited, Algebra, Geometry, and Software Systems. Springer, Berlin (2003)","DOI":"10.1007\/978-3-662-05148-1"},{"key":"104_CR43","doi-asserted-by":"crossref","unstructured":"Joswig, M., Loho, G., Lorenz, B., Schr\u00f6ter, 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\u201313, 2015, Revised Selected Papers, Lecture Notes in Comput. Sci., vol. 9582, pp 429\u2013445, Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-32859-1_37"},{"key":"104_CR44","doi-asserted-by":"crossref","unstructured":"Joswig, M., Theobald, T.: Polyhedral and algebraic methods in computational geometry, Universitext, Springer, London, 2013, Revised and updated translation of the 2008 German original","DOI":"10.1007\/978-1-4471-4817-3"},{"key":"104_CR45","doi-asserted-by":"crossref","unstructured":"Joswig, M., Ziegler, G. M.: Convex hulls, oracles, and homology. J. Symbolic Comput. 38(4), 1247\u20131259 (2004)","DOI":"10.1016\/j.jsc.2003.08.006"},{"key":"104_CR46","doi-asserted-by":"crossref","unstructured":"Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V.: Generating all vertices of a polyhedron is hard. Discrete Comput. Geom. 39(1\u20133), 174\u2013190 (2008)","DOI":"10.1007\/s00454-008-9050-5"},{"key":"104_CR47","unstructured":"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.\u00a0159\u2013175, Academic Press, New York (1972)"},{"key":"104_CR48","unstructured":"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.\u00a053\u201359 (2008)"},{"key":"104_CR49","doi-asserted-by":"crossref","unstructured":"K\u00f6ppe, M.: A primal Barvinok algorithm based on irrational decompositions. SIAM J. Discrete Math. 21(1), 220\u2013236 (electronic) (2007)","DOI":"10.1137\/060664768"},{"key":"104_CR50","doi-asserted-by":"crossref","unstructured":"McMullen, P.: The numbers of faces of simplicial polytopes. Israel J. Math. 9, 559\u2013570 (1971)","DOI":"10.1007\/BF02771471"},{"key":"104_CR51","unstructured":"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.\u00a051\u201373, Princeton University Press, Princeton, (1953)"},{"key":"104_CR52","doi-asserted-by":"crossref","unstructured":"Murai, S., Nevo, E.: On the generalized lower bound conjecture for polytopes and spheres. Acta Math. 210(1), 185\u2013202 (2013)","DOI":"10.1007\/s11511-013-0093-y"},{"key":"104_CR53","unstructured":"Opfer, T.: Entwicklung eines exakten rationalen dualen Simplex-L\u00f6sers, Master\u2019s thesis, TU Darmstadt, (2011)"},{"key":"104_CR54","unstructured":"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)"},{"key":"104_CR55","unstructured":"The polymake team, polymake, version 2.14, http:\/\/www.polymake.org (2015)"},{"key":"104_CR56","doi-asserted-by":"crossref","unstructured":"Lo\u00efc, P.: The Euclidean algorithm in dimension $$n$$ n , ISSAC \u201996. Proceedings of the 1996 international symposium on Symbolic and algebraic computation, pp.\u00a040\u201342 (1996)","DOI":"10.1145\/236869.236894"},{"key":"104_CR57","unstructured":"Rehn, T.: Polyhedral description conversion up to symmetries, Master\u2019s thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg, (2010)"},{"key":"104_CR58","unstructured":"Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency. Vol. C, Algorithms and Combinatorics, vol.\u00a024, pp. 70\u201383, Springer-Verlag, Berlin, Disjoint paths, hypergraphs, Chapters (2003)"},{"key":"104_CR59","unstructured":"Seidel, R.: A convex hull algorithm optimal for point sets in even dimensions. Tech. report, University of British Columbia, Department of Computer Science (1981)"},{"key":"104_CR60","unstructured":"Tantau, T.: TikZ ist kein Zeichenprogramm PGF\/TikZ, http:\/\/www.ctan.org\/tex-archive\/graphics\/pgf\/"},{"key":"104_CR61","unstructured":"The CGAL Project, CGAL user and reference manual, 4.7 ed., CGAL Editorial Board, (2015)"},{"issue":"3","key":"104_CR62","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"104_CR63","unstructured":"Verdoolaege, S.: barvinok, http:\/\/barvinok.gforge.inria.fr\/"},{"key":"104_CR64","unstructured":"Walter, M.: Unimodularity-test extension for polymake, https:\/\/github.com\/xammy\/unimodularity-test"},{"key":"104_CR65","doi-asserted-by":"crossref","unstructured":"Walter, M., Truemper, K.: Implementation of a unimodularity test. Math. Program. Comput. 5(1), 57\u201373 (2013)","DOI":"10.1007\/s12532-012-0048-x"},{"key":"104_CR66","doi-asserted-by":"crossref","unstructured":"Ziegler, G.M.: Lectures on polytopes, Graduate Texts in Mathematics, vol. 152. Springer-Verlag, New York (1995)","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-016-0104-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12532-016-0104-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-016-0104-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-016-0104-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T19:06:33Z","timestamp":1748977593000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12532-016-0104-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,23]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["104"],"URL":"https:\/\/doi.org\/10.1007\/s12532-016-0104-z","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,23]]}}}