Collaborative Research: Almost Symmetric Integer Programs

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

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.