权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Geometry and Algorithms for Exploiting Polyhedral Symmetries

利用多面体对称性的几何和算法

基本信息

批准号：
263949937
负责人：
Professor Dr. Achill Schürmann
金额：
--
依托单位：
Institut für Mathematik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2015
资助国家：
德国
起止时间：
2014-12-31 至 2017-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/263949937?language=en
关键词：
Geometry Algorithms 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.

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