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.