Geometry and Algorithms for Exploiting Polyhedral Symmetries
Final Report Abstract
Main aim of this research project was to get a better understanding of polyhedral symmetries and making advancements in using them in practical polyhedral computations. The underlying long term vision being that symmetry-exploiting algorithms will become standard tools in polyhedral computations, so that they are used in mathematical software whenever symmetry is available. Any progress towards this goal has a significant long-term impact on diverse mathematical disciplines and applications, since polyhedral computations are widely used. During the course of this project, new theories for the better understanding of affine symmetry groups of polytopes have been developed. We have in particular answered when a given matrix group implies additional affine symmetries for any orbit polytope having it as its symmetry group. We have solved several difficult polyhedral representation conversion problems, with applications ranging from the classification of Dirichlet-Voronoi polyhedra of lattices to cohomology computations based on reduction theories of quadratic forms. For the study of symmetric integer linear programming problems, a new notion of normalizer equivalence has been introduced and studied. Reformulations based on it and other symmetry exploiting techniques have been shown to work on specific test instances. For the theory of lattice point counting we have introduced a new type of local formula, in which symmetries can be exploited. For several concrete computational problems in voting theory, we have used symmetry exploiting techniques. Subsuming, the project was very successful, also in some unexpected ways. For several specific problems, we successfully applied new symmetry exploiting techniques. However, a lot of further research will be necessary to turn symmetryexploiting algorithms into standard tools in polyhedral computations.
Publications
- Affine Symmetries of Orbit Polytopes, Adv. Math., 288 (2016), 386–425
Erik Friese and Frieder Ladisch
(See online at https://doi.org/10.1016/j.aim.2015.10.021) - Realizations of abstract regular polytopes from a representation theoretic view Aequationes Math., 90 (2016), 1169–1193
Frieder Ladisch
(See online at https://doi.org/10.1007/s00010-016-0434-y) - The complete classification of five-dimensional Dirichlet-Voronoi polyhedra of translational lattices, Acta Crystallographica, A72 (2016), 673–683
Mathieu Dutour Sikirić, Alexey Garber, Achill Schürmann, Clara Waldmann
(See online at https://doi.org/10.1107/S2053273316011682) - The impact of dependence among voters preferences with partial indifference, Quality & Quantity, 51 (2017), 2793–2812
Erik Friese, William V. Gehrlein, Dominique Lepelley, Achill Schürmann
(See online at https://doi.org/10.1007/s11135-016-0446-7) - A property of the Birkhoff polytope, Algebraic Combinatorics, 1 (2018), no. 2, p. 275–281
Barbara Baumeister and Frieder Ladisch
(See online at https://doi.org/10.5802/alco.6) - Equivalence of Lattice Orbit Polytopes, SIAM J. on Appl. Alg. Geom., 2 (2018), 259–280
Frieder Ladisch and Achill Schürmann
(See online at https://doi.org/10.1137/17M1120130)
