# The Complexity of Valued Constraints

1st October 2007 to 30th September 2010

This proposal is a collaborative application 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. We are seeking
funding to extend and develop a novel algebraic theory of complexity for valued constraint satisfaction problems. Constraint
satisfaction problems arise in many practical problems, such as scheduling and circuit layout, so this family of problems
has been widely studied in computer science. All known algorithms for the most general form of the problem require exponential
time, and are therefore impractical for large cases. However, several restrictions have been identified which are sufficient
to make the restricted form of the problem efficiently solvable. In fact, a careful mathematical analysis of the problem has
shown that the computational difficulty of any particular constraint satisfaction problem is closely related to certain algebraic
properties of the constraints. In this research project we are seeking to develop a new algebraic approach to an even wider
class of problems which involve both constraint satisfaction and optimisation. Such problems are called valued constraint
problems. We hope to show that by using general algebraic methods we can identify all types of valued constraints which can
be efficiently optimised. We also plan to implement the techniques we develop in new software tools which can be use to analyse
any given example of a valued constraint problem, and solve it using special-purpose efficient methods when these are applicable.