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.