Collaborative Research: Almost Symmetric Integer Programs

合作研究：几乎对称整数规划

• 批准号: 1333789
• 负责人: Sebastian Pokutta
• 金额: $ 17万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1333789&HistoricalAwards=false
• 关键词: Collaborative; Research; Almost; Symmetric; Integer

The objective of this collaborative research award is to develop techniques that exploit almost symmetry in integer programming. In the past decade, the exploitation of regular symmetries has led to a dramatic decrease in computation time for many classes of integer programming problems. Unfortunately, many of these problems, perhaps due to measurement or modeling error, are only close to being symmetric; minuscule differences in coefficients can hide exact symmetries. These almost symmetries are permutations that can become exact symmetries when the problem instance is modified slightly. This project seeks to expand the concept of symmetry to include almost symmetries and will develop a framework to treat almost symmetries as if they are actual symmetries. This will significantly broaden the class of optimization problem that can benefit from symmetry-exploiting techniques, resulting in improved computational times for a wider class of problems. This project will develop software that identifies almost symmetries and used to identify the prevalence of almost symmetries and assess how the existence of almost symmetries affect the difficulty of an integer programming instance. Algorithms designed to exploit almost symmetries will be developed and tested. If successful, this project will make advances not just to integer programming, but to a wider set disciplines including graph theory, algebra, and data mining applications, as symmetries and almost symmetries pervade all the sciences, in particular engineering and mathematics. The techniques developed will allow the solving of large-scale real-world problems that are currently unsolvable. The developed software will be made available under a suitable open source license so that other researchers can build on our work and integrate it into their projects.

该合作研究奖的目标是开发利用整数规划中几乎对称性的技术。在过去的十年中，正则对称性的利用使得许多类型的整数规划问题的计算时间显着减少。不幸的是，这些问题中的许多（可能是由于测量或建模误差）仅接近对称；系数的微小差异可能会隐藏精确的对称性。这些几乎对称性是排列，当问题实例稍微修改时可以变成精确对称性。该项目旨在扩展对称的概念以包括几乎对称，并将开发一个框架来将几乎对称视为真正的对称。这将显着拓宽可以受益于对称性利用技术的优化问题的类别，从而缩短更广泛类别问题的计算时间。该项目将开发识别几乎对称性的软件，用于识别几乎对称性的普遍性，并评估几乎对称性的存在如何影响整数编程实例的难度。将开发和测试旨在利用几乎对称性的算法。如果成功，该项目不仅将推动整数规划的进步，还将推动包括图论、代数和数据挖掘应用在内的更广泛学科的进步，因为对称性和几乎对称性遍及所有科学，特别是工程和数学。所开发的技术将能够解决目前无法解决的大规模现实问题。开发的软件将在适当的开源许可下提供，以便其他研究人员可以在我们的工作基础上进行构建并将其集成到他们的项目中。