|
| EPSRC Reference: |
EP/C525949/1 |
| Title: |
Tractability of Constraint Problems: Unification, Extension and Applicability |
| Principal Investigator: |
Professor D Cohen |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Computer Science |
| Organisation: |
Royal Holloway, Univ of London |
| Scheme: |
Standard Research |
| Starts: |
01 October 2005 |
Ends: |
30 September 2008 |
Value (£): |
184,410
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
This proposal concerns the broad class of computational problems known as "constraint satisfaction problems". We aim to develop a more powerful and general theory of tractability for these problems which takes into account both the nature of the constraints and the structural properties of the way different constraints interact. This theory will be a major step forward in understanding and exploiting the various different aspects of a constraint problem that can make it feasible to solve.
As an application of this new theory we plan to extend existing decomposition methods for these problems by using more sophisticated criteria to identify suitable components. At present, all decomposition methods ignore the nature of the constraints in the components they identify. We expect to be able to identify components of a given problem that are tractable for a variety of different reasons, including the constraint languages used in those components. We believe that we may discover a small number of design patterns describing common properties of many CSP instances, which can be used to guide the choice of solution algorithm.
We plan to implement the ideas developed in flexible and robust software tools that can be used by non-specialists to apply the new analysis and decomposition techniques to a wide range of constraint problems.
|
| Final Report Summary |
This proposal concerns the broad class of computational problems known as "constraint satisfaction problems". We aim to develop a more powerful and general theory of tractability for these problems which takes into account both the nature of the constraints and the structural properties of the way different constraints interact. This theory will be a major step forward in understanding and exploiting the various different aspects of a constraint problem that can make it feasible to solve.
As an application of this new theory we plan to extend existing decomposition methods for these problems by using more sophisticated criteria to identify suitable components. At present, all decomposition methods ignore the nature of the constraints in the components they identify. We expect to be able to identify components of a given problem that are tractable for a variety of different reasons, including the constraint languages used in those components. We believe that we may discover a small number of design patterns describing common properties of many CSP instances, which can be used to guide the choice of solution algorithm.
We plan to implement the ideas developed in flexible and robust software tools that can be used by non-specialists to apply the new analysis and decomposition techniques to a wide range of constraint problems.
|
| Further Information: |
|
| Organisation Website: |
http://www.rhul.ac.uk |
|
|