| EPSRC Reference: |
EP/C533461/1 |
| Title: |
Symmetry & Integer Programming |
| Principal Investigator: |
Maros, Professor I |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computing |
| Organisation: |
Imperial College London |
| Scheme: |
Postdoctoral Mobility PreFEC |
| Starts: |
01 September 2005 |
Ends: |
31 August 2006 |
Value (£): |
75,948
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Mathematical Aspects of OR |
| Parallel Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
W e are proposing a new technique for the practical solution of problems concerning the efficient allocation of indivisible objects, such as allocating people to tasks, boxes to containers and airplanes to scheduled flights. For example, we may want to place boxes of given dimensions as many as possible in a container of finite capacity. Now there may be some symmetry in the problem. In the boxes example, we may regard all boxes with the same dimensions as being essentially the same. Similarly, a solution to the problem may have symmetry: two boxes with the same dimensions may be interchanged without changing the solution in any essential way. Other problems and solutions may have symmetry that is less obvious. Our aim in this project is to research the determination and exploitation of symmetry in the general class of integer programming problems, which can be extremely difficult, but highly important for a wide range of applications in business, industry and finance. The main idea is that if a good solution to one of these problems exhibits symmetry, then we shall be able to find such a solution using our technique much more quickly, whereas more traditional methods would take a prohibitively long time to obtain a solution.Our technique is based on an important theoretical branch of algebra called group theory, which is the abstract study of symmetry. Using group theoretical methods, we shall develop theory and software to determine the symmetries of an integer programming problem, and then using further theory and computation we shall determine candidates for groups of symmetries of solutions to that problem. These candidates then can be used to collapse our integer programming problem into smaller ones, which will be easier to solve than the original problem.In practice, integer programming problems are solved by sophisticated computer programs running on high-performance computer systems. Accordingly, we plan to run our theoretical investigation hand in hand with the implementation of related software using a very high level object oriented language. W e also plan to investigate the use of massively parallel techniques (on a computing GRID) to explore the application of large numbers of candidate solution symmetry groups at once.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.imperial.ac.uk |