EPSRC Reference: 
EP/C533461/1 
Title: 
Symmetry & Integer Programming 
Principal Investigator: 
Maros, Professor I 
Other Investigators: 

Researcher CoInvestigators: 

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 highperformance 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 nonacademic 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 