365体育网站

365体育网站Advertisement

Exploiting Symmetries in Polyhedral Computations

  • Achill SchürmannEmail author
Chapter
Part of the Fields Institute Communications book series (FIC, volume 69)

Abstract

365体育网站In this note we give a short overview on symmetry exploiting techniques in three different branches of polyhedral computations: The representation conversion problem, integer linear programming and lattice point counting. We describe some of the future challenges and sketch some directions of potential developments.

Key words

Polyhedral computations Symmetry Representation conversion Integer linear programming Ehrhart theory Volume computations 

Subject Classifications

52Bxx 90C10 11P21 

References

  1. 1.
    Baldoni, V., Berline, N., De Loera, J.A., öppe, M.K, Vergne, M.: How to integrate a polynomial over a simplex. Math. Comp. 80(273), 297–325 (2011)
  2. 2.
    Baldoni, V., Berline, N., De Loera, J.A., öppe, M.K., Vergne, M.: Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. Found. Comput. Math. (2011, to appear). Preprint at arxiv:1011.1602
  3. 3.
    Ballinger, B., Blekherman, G., Cohn, H., Giansiracusa, N., Kelly, E., Schürmann, A.: Experimental study of energy-minimizing point configurations on spheres. Experiment. Math. 18, 257–283 (2009)
  4. 4.
    Barvinok, A.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19, 769–779 (1994)
  5. 5.
    Barvinok, A.: Integer points in polyhedra. Eur. Math. Soc., Zrich, pp. viii+191 (2008).
  6. 6.
    Beck, M., Pixton, D.: The Ehrhart polynomial of the Birkhoff polytope. Discrete Comput. Geom. 30, 623–637 (2003). See also the update in arxiv:math/0305332
  7. 7.
    Beck, M., Robins, S., Computing the continuous discretely. Springer, New York (2007)
  8. 8.
    Berenstein, A.D., Zelevinsky, A.V.: Tensor product multiplicities, canonical bases and totally positive varieties. Invent. Math. 143, 77–128 (2001)
  9. 9.
    Bödi, R., Herr, K., Joswig, M.: Algorithms for highly symmetric linear and integer programs. Math. Program. A (2012, to appear). Published online,
  10. 10.
    Bremner, D., Dutour Sikirić, M., Pasechnik, D.V., Rehn, T., Schürmann, A.: Computing symmetry groups of polyhedra. Preprint at arxiv:1210.0206
  11. 11.
    Bremner, D., Dutour Sikirić, M., Schürmann, A.: Polyhedral representation conversion up to symmetries. In: CRM Proceedings & Lecture Notes, Montreal, vol. 48, pp. 45–71. AMS, (2009)
  12. 12.
    Brightwell, G., Winkler, P.: Counting linear extensions. Order 8, 225–242 (1991)
  13. 13.
    Bruns, W., Söger, C.: The computation of generalized Ehrhart series in Normaliz. Preprint at arxiv:1211.5178
  14. 14.
    Bulutoglu, D.A., Margot, F.: Classification of orthogonal arrays by integer programming. J. Stat. Plan. Inference 138, 654–666 (2008)
  15. 15.
    Christof, T., Reinelt, G.: Combinatorial optimization and small polytopes. Top 4, 1–64 (1996)
  16. 16.
    Christof, T., Reinelt, G.: Decomposition and parallelization techniques for enumerating the facets of combinatorial polytopes. Internat. J. Comput. Geom. Appl. 11, 423–437 (2001)
  17. 17.
    Cohn, H., Kumar, A.: Optimality and uniqueness of the Leech lattice among lattices. Ann. Math. 170, 1003–1050 (2009)
  18. 18.
    Conway, J.H., Curtis, R.T., Norton, S.P., Parker, R.A., Wilson, R.A.: Atlas of finite groups. Oxford University Press, Oxford (1985)
  19. 19.
    De Loera, J.A.: The many aspects of counting lattice points in polytopes. Math. Semesterber. 52, 175–195 (2005)
  20. 20.
    Deza, A., Fukuda, K., Mizutani, T., Vo, C.: On the face lattice of the metric polytope. In: Discrete and Computational Geometry. LNSC, vol. 2866, pp. 118–128. Springer, New York (2003)
  21. 21.
    Deza, A., Fukuda, K., Pasechnik, D., Sato, M.: On the skeleton of the metric polytope. In: Discrete and Computational Geometry. LNSC, vol. 2098, pp. 125–136. Springer, New York (2001)
  22. 22.
    Deza, A., Indik, G.: A counterexample to the dominating set conjecture. Optim. Lett. 1–2, 163–169 (2007)
  23. 23.
    Diaconis, P., Sturmfels, B.: Algebraic algorithms for sampling from conditional distributions. Ann. Stat. 26, 363–397 (1998)
  24. 24.
    Dutour Sikirić, M., Schürmann, A., Ellis, G.: On the integral homology of \(\mbox{ PSL}_{4}(\mathbb{Z})\) and other arithmetic groups. J. Number Theory 131, 2368–2375 (2011)
  25. 25.
    Dutour Sikirić, M., Schürmann, A., Vallentin, F.: Classification of eight dimensional perfect forms. Electron. Res. Announc. Am. Math. Soc. 13, 21–32 (2007)
  26. 26.
    Dutour Sikirić, M., Schürmann, A., Vallentin, F.: Complexity and algorithms for computing Voronoi cells of lattices. Math. Comp. 78, 1713–1731 (2009)
  27. 27.
    Dutour Sikirić, M., Schürmann, A., Vallentin, F.: The contact polytope of the Leech lattice. Discret. Comput. Geom. 44, 904–911 (2010)
  28. 28.
    Dyer, M.E., Frieze, A.M.: On the complexity of computing the volume of a polyhedron. SIAM J. Comput. 17, 967–974 (1988)
  29. 29.
    Ehrhart, E.: Sur un problème de géométrie diophantienne linéaire. I. Polyèdres et réseaux. J. Reine Angew. Math. 226, 1–29 (1967)
  30. 30.
    Friedman, E.J.: Fundamental domains for integer programs with symmetries. In: Combinatorial Optimization and Applications. LNSC, vol. 4616, pp. 146–153. Springer, New York (2007)
  31. 31.
    Gehrlein, W.V., Lepelley, D.: Voting paradoxes and group coherence Springer, Berlin/London (2011)
  32. 32.
    Gowers, W.T.: Rough structure and classification. In: Visions in Mathematics – Towards 2000, pp. 79–117. Birkhäuser, Basel (2000)
  33. 33.
    Grünbaum, B.: In: Kaibel, V., Klee, V., Ziegler, G.M. (eds. ) Convex Polytopes, 2nd edn. Springer, London/New York (2003)
  34. 34.
    Hales, T.C.: A proof of the Kepler conjecture. Ann. Math. 162, 1065–1185 (2005)
  35. 35.
    Hales, T.C.: The strong dodecahedral conjecture and fejes toth’s conjecture on sphere packings with kissing number twelve. Preprint at arxiv:1110.0402
  36. 36.
    Herr, K., Rehn, T., Schürmann, A.: Exploiting symmetry in integer convex optimization using core points. Preprint at arxiv:1202.0435
  37. 37.
    Holt, D.F., Eick, B., O’Brien, E.A.: Handbook of computational group theory. Chapman & Hall/CRC, Boca Raton (2005)
  38. 38.
    Kaibel, V., Pfetsch, M.E.: Packing and partitioning orbitopes. Math. Program. A 114, 1–36 (2008)
  39. 39.
    Kaibel, V., Schwartz, A.: On the complexity of polytope isomorphism problems. Graphs Combin. 19, 215–230 (2003)
  40. 40.
    Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)
  41. 41.
    Kaski, P., Östergård, P.R.J.: Classification algorithms for codes and designs. Springer, Berlin (2006)
  42. 42.
    Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V.: Generating all vertices of a polyhedron is hard. Discrete Comput. Geom. 39, 174–190 (2008)
  43. 43.
    Knutson, A., Tao, T.: The honeycomb model of \(\mathrm{GL}_{n}(\mathbb{C})\) tensor products I. Proof of the saturation conjecture. J. Amer. Math. Soc. 12, 1055–1090 (1999)
  44. 44.
    Kumar, A.: Elliptic fibrations on a generic Jacobian Kummer surface. J. Algebraic. Geom. (2012, to appear). Preprint at arxiv:1105.1715
  45. 45.
    Lasserre, J.B.: Linear and integer programming vs linear integration and counting. Springer, New York/London (2009)
  46. 46.
    Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)
  47. 47.
    Leon, J.S.: Permutation group algorithms based on partitions. I. Theory and algorithms. J. Symbolic Comput. 12, 533–583 (1991)
  48. 48.
    Linderoth, J., Margot, F., Thain, G.: Improving bounds on the football pool problem via symmetry reduction and high-throughput computing. Inf. J. Comput. 21, 445–457 (2009)
  49. 49.
    Luks, E.M.: Permutation groups and polynomial-time computation. In: Groups and Computation, pp. 139–175. AMS, Providence (1993)
  50. 50.
    Margot, F.: Exploiting orbits in symmetric ILP. Math. Program. B 98, 3–21 (2003)
  51. 51.
    Margot, F.: Symmetry in integer linear programming. In: 50 Years of Integer Programming, pp. 647–686. Springer, Berlin/London (2010)
  52. 52.
    Martinet, J.: Perfect Lattices in Euclidean Spaces. Springer, Berlin/New York (2003)
  53. 53.
    McMullen, P., Schulte, E.: Abstract Regular Polytopes. Cambridge University Press, Cambridge/New York (2002)
  54. 54.
    Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Math. Program. A 126, 147–178 (2011)
  55. 55.
    Rehn, T.: Fundamental permutation group algorithms for symmetry computation. Diploma Thesis in Computer Science, OvG University Magdeburg (2010)
  56. 56.
    Rehn, T., Schürmann, A.: C++ tools for exploiting polyhedral symmetries. In: Mathematical Software – ICMS 2010. LNCS, vol. 6327, pp. 295–298. Springer, Berlin (2010)
  57. 57.
    Robertson, S.A.: Polytopes and Symmetry. Cambridge University Press, Cambridge/New York (1984)
  58. 58.
    Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176, 383–412 (2012)
  59. 59.
    Schrijver, A.: Theory of linear and integer programming. Wiley, Chichester/New York (1986)
  60. 60.
    Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency, vols. A, B, C. Springer, Berlin (2003)
  61. 61.
    Schürmann, A.: Computational geometry of positive definite quadratic forms. AMS, Providence (2009)
  62. 62.
    Schürmann, A.: Exploiting polyhedral symmetries in social choice. Social Choice and Welfare (2012, to appear). Published online, , preprint at arxiv:1109.1545
  63. 63.
    Schuster, S., Hlgetag, C.: On elementary flux modes in biochemical reaction systems at steady state. J. Biol. Syst. 2, 165–182 (1994)
  64. 64.
    Seress, Á.: Permutation group algorithms. Cambridge University Press, New York (2003)
  65. 65.
    Stanley, R.P.: Enumerative Combinatorics, vol. 1. Cambridge University Press, Cambridge/New York (1997)
  66. 66.
    Todd, M.J.: The many facets of linear programming. Math. Program. B 91, 417–436 (2002)
  67. 67.
    Wilson, M.C., Pritchard, G.: Probability calculations under the IAC hypothesis. Math. Soc. Sci. 54, 244–256 (2007)
  68. 68.
    Wolsey, L.A.: Integer Programming. Wiley, New York (1998)
  69. 69.
    Ziegler, G.M.: Lectures on Polytopes. Springer, New York (1997)

Software and Webpages

  1. Counting lattice points,
  2. Graph and labeling automorphisms,
  3. Double Description,
  4. Mathematical programming technology,
  5. Groups, Algorithms, Programming,
  6. High-level memory optimizations,
  7. Graph Visualization Software,
  8. High-end libraries for math programming,
  9. Lattice point count, volumes and integrals,
  10. Lexicographic reverse search,
  11. Computational Algebra System,
  12. Classification of finite groups of isometries,
  13. Mixed Integer Problem Library,
  14. Graph and labeling automorphisms,
  15. Permutation groups library,
  16. A polyhedral GAP package,
  17. A framework for analyzing convex polytopes,
  18. Solving Constraint Integer Programs,
  19. Symmetric IP problems,
  20. Symmetric polyhedra toolkit,

Copyright information

© Springer International Publishing Switzerland 2013

Authors and Affiliations

  1. 1.Institute of MathematicsUniversity of RostockRostockGermany

Personalised recommendations