EPSRC logo

Details of Grant 

EPSRC Reference: EP/C533461/1
Title: Symmetry & Integer Programming
Principal Investigator: Maros, Professor I
Other Investigators:
Soicher, Professor LH Dobcsanyi, Dr P
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
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
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