|
| EPSRC Reference: |
GR/S87454/01 |
| Title: |
Tractable Valued Consraints: An Algebraic Approach. |
| Principal Investigator: |
Professor PG Jeavons |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Computing Laboratory |
| Organisation: |
University of Oxford |
| Scheme: |
Standard Research |
| Starts: |
20 June 2004 |
Ends: |
19 June 2006 |
Value (£): |
20,759
|
| EPSRC Research Topic Classifications: |
| Artificial Intelligence Technologies |
Fundamentals of Computing |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
This proposal is a collaborative application involving Dr Peter Jeavons at the University of Oxford, Dr David Cohen at Royal Holloway, University of London, and Dr Martin Cooper at the University of Toulouse III, France. We are seeking funding to enable Dr Cooper to visit Dr Jeavons and Dr Cohen for 2 periods of 3 months in 2004 and 2005.
Dr Cooper is a specialist in consistency techniques for the family of computational problems known as "constraint satisfaction problems". This family of problems has been widely studied in computer science, and a number of tractable sub-cases of the constraint satisfaction problem have been identified using algebraic techniques. We have recently established that similar techniques can be devised to identify tractable cases of the more general "valued constraint satisfaction problem". This is a very general framework which includes many standard forms of optimisation problem, so tractable classes for this problem are of interest for many practical optimisation problems. In this project we aim to obtain a complete description of all the tractable cases for some important special cases of the valued constraint satisfaction problem. We also aim to identify new tractable cases of the general problem and to develop a strong algebraic theory of the complexity of optimisation problems.
|
| Final Report Summary |
This project was a collaboration involving Professor Peter Jeavons at the University of Oxford, Professor David Cohen at Royal Holloway, University of London, and Dr Martin Cooper at the University of Toulouse III, France. The funding for the project enabled Dr Cooper to visit Prof Jeavons and Prof Cohen for 2 extended research visits in 2004 and 2005.
Dr Cooper is a specialist in consistency techniques for the family of computational problems known as "constraint satisfaction problems". This family of problems has been widely studied in computer science, and a number of tractable sub-cases of the constraint satisfaction problem have been identified using algebraic techniques. Our research has established that similar techniques can be used to identify tractable cases of the more general "valued constraint satisfaction problem". This is a very general framework which includes many standard forms of optimisation problem, so tractable classes for this problem are of interest for many practical optimisation problems. In this project we obtained a complete description of all the tractable cases for some important special cases of the valued constraint satisfaction problem. We also identified new tractable cases of the general problem and developed a strong algebraic theory of the complexity of optimisation problems defined by valued constraints.
|
| Further Information: |
http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/index.html |
| Organisation Website: |
http://www.ox.ac.uk |
|
|