EPSRC Reference: 
EP/L021226/1 
Title: 
Constraint Network Tractability: Beyond Structure and Language 
Principal Investigator: 
Jeavons, Professor PG 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science 
Organisation: 
University of Oxford 
Scheme: 
Standard Research 
Starts: 
17 May 2014 
Ends: 
16 May 2017 
Value (£): 
114,386

EPSRC Research Topic Classifications: 
Fundamentals of Computing 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
04 Feb 2014

EPSRC ICT Responsive Mode  Feb 2014

Announced


Summary on Grant Application Form 
The Constraint Satisfaction Problem (or CSP) is a general framework for all kinds of computational problems that involve searching for a set of values that together satisfy some specified restrictions, known as constraints. Such problems are encountered in a very large range of applications, including classic problems in operations research and artificial intelligence, many forms of scheduling and planning problems, and problems in cryptography, computer vision, chemical synthesis and gene matching.
The Maximum Constraint Satisfaction Problem (or MaxCSP) is a generalisation of the CSP whose range of application is even greater: it includes many combinatorial optimisation problems that are not easily expressed in the basic CSP framework. In this problem the aim is to find an assignment of values to the variables of the problem which maximises the number of satisfied constraints.
Both the CSP and the MaxCSP are NPhard, which means that it is unlikely that there exist efficient general algorithms that can solve all instances of such problems. Thus one can try to design heuristics which perform well on certain kinds of instances, or else one can restrict the general problem in order to obtain a more tractable problem (for example, a problem which can be solved in polynomial time). Most of our research is concerned with the second approach: we try to identify the restrictions on constraint satisfaction problems which are sufficient to ensure they can be solved efficiently.
In this project we aim to find a novel approach to defining such restrictions that is more powerful than anything that has been considered before, and allows us to identify many more kinds of tractable problems. In the past, the only kinds of tractable problems that have been considered fall into two distinct classes. In the first, the constraints are arbitrary, but they can only be applied to the variables in limited ways. In the second, the constraints fall into a restricted family of constraint types, but they can be applied to the variables in an arbitrary way. Both of these kinds of restrictions have led to interesting mathematical theories, and some important special cases which can be solved efficiently. However, we believe that it is now possible to combine these approaches and obtain a much more general theory that unifies the previous approaches, and provides a more flexible way to define the restrictions on problems.
By developing this more powerful approach we hope to be able to describe much more accurately which kinds of constraint problems can be solved efficiently, and to use this information to improve the available software tools and analytical techniques.

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.ox.ac.uk 