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.
