| EPSRC Reference: |
EP/C525949/1 |
| Title: |
Tractability of Constraint Problems: Unification, Extension and Applicability |
| Principal Investigator: |
Cohen, Professor D |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Royal Holloway, Univ of London |
| Scheme: |
Standard Research (Pre-FEC) |
| 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 on Grant Application Form |
|
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.
|
|
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: |
|