Geometry and Algorithms for Exploiting Polyhedral Symmetries

数学及其应用中的许多重要问题都是使用线性约束来建模的。它们定义的几何对象是多面体。标准建模通常产生具有许多对称性的多面体，如旅行推销员或分配多面体。然而，分支和定界方法等标准算法没有利用这一点。通常，它们在对称问题上的工作尤其糟糕，尽管有复杂的数学工具可以用来处理这种对称问题。在这个项目中，我们将为多面体计算中的基本任务建立新的对称性开发技术：表示转换问题、整数线性规划、格点计数和精确体积计算。我们将在数几何和计算群论等学科的丰富基础上开发新的技术。新的理论和算法工具的发展将伴随着计算机辅助的挑战性数学问题的工作，这些问题来自不同的领域，如数论、组合学和社会选择。通过这种方式，我们将在两个方向上弥合数学优化和纯数学之间的鸿沟。我们的工作将导致公开可用的软件的创建，为其他数学家打开新的研究可能性。由于理论和算法的进步将有助于在未来的许多计算中利用可用的对称性，这个项目将产生重大的长期影响，远远超出其直接范围。

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.