Geometry and Algorithms for Exploiting Polyhedral Symmetries

• Applicant: Professor Dr. Achill Schürmann
• Subject Area: Mathematics
• Term: from 2015 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 263949937

Many important problems in mathematics and its applications are modeled using linear constraints. The geometric objects they define are polyhedra. Standard modeling often yields polyhedra having many symmetries, like the travelling salesman or assignment polyhedra. However, standard algorithms like branch and bound methods do not take advantage of this. Often they even work particularly poorly on symmetric problems, despite the fact that there are elaborate mathematical tools available to deal with such symmetries. In this project we will establish new symmetry-exploiting techniques for fundamental tasks in polyhedral computations: the representation conversion problem, integer linear programming, lattice point counting and exact volume computations. We will develop new techniques by building upon the rich foundations from disciplines such as the Geometry of Numbers and Computational Group Theory. The development of new theoretical and algorithmic tools will go along with computer-assisted work on challenging mathematical problems, coming from diverse areas such as Number Theory, Combinatorics and Social Choice. In this way we will bridge the gap between Mathematical Optimization and Pure Mathematics in both directions. Our work will lead to the creation of publicly available software, opening new research possibilities for other mathematicians. As the theoretical and algorithmic advances will help to exploit available symmetry in numerous future computations, this project will have a significant long-term impact, far beyond its immediate scope.

• DFG Programme: Research Grants