| NSF Org: |
CMMI Division of Civil, Mechanical, and Manufacturing Innovation |
| Recipient: |
|
| Initial Amendment Date: | August 15, 2013 |
| Latest Amendment Date: | August 15, 2013 |
| Award Number: | 1333789 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Georgia-Ann Klutke
gaklutke@nsf.gov (703)292-2443 CMMI Division of Civil, Mechanical, and Manufacturing Innovation ENG Directorate for Engineering |
| Start Date: | September 1, 2013 |
| End Date: | August 31, 2017 (Estimated) |
| Total Intended Award Amount: | $170,000.00 |
| Total Awarded Amount to Date: | $170,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
926 DALNEY ST NW ATLANTA GA US 30318-6395 (404)894-4819 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
225 North Avenue, NW Atlanta GA US 30332-0002 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | OPERATIONS RESEARCH |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.041 |
ABSTRACT
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The major goals of this project were to gain a better understanding of the role of generalized symmetries in the context of linear and semidefinite programming. The focus was in particular on so-called 'almost symmetries', which capture problems that are not fully symmetric but whose problem formulation is almost symmetric. The obtained results significantly improved the understanding of these generalized symmetry concepts and provided critical insights for real-world problem solving.
Within the duration of this grant we explored almost symmetries both from a computational as well as a theoretical point of view. In particular:
1) Together with our project partner at UT, we developed a software that detects almost symmetries in graphs that then in turn can be naturally applied to graphs arising from problem formulations. Once this detection phase is over the obtained symmetry information can be used, e.g., in commercial solvers for efficient management.
2) We demonstrated that (almost) symmetries can induce fundamental limits towards obtaining small compact problem formulations. These fundamental limits cannot be overcome by traditional approaches and provide a fundamental barrier for certain problem types.
3) We generalized Yannakakis' breakthrough result for symmetric linear programming formulations for the matching problem as well as the traveling salesman problem to the more general semidefinite programming case showing that there is no small semidefinite programming formulation for the matching problem and that for the traveling salesman problem the Lasserre formulation provides an optimal tradeoff.
As such the project significantly advanced our understanding of symmetries in the context of linear and semidefinite programming and provided insights into the concept of almost symmetries that has been studied in the context of this award.
Last Modified: 12/03/2017
Modified by: Sebastian Pokutta
Please report errors in award information by writing to: awardsearch@nsf.gov.
