Constraint Network Tractability: Beyond Structure and Language
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.
Selected Publications

Binarisation via dualisation for valued constraints
David A. Cohen‚ Martin C. Cooper‚ Peter Jeavons and Stanislav Živný
In Proceedings of the Twenty−Ninth AAAI Conference on Artificial Intelligence. Pages 3731–3737. AAAI Press. 2015.
Details about Binarisation via dualisation for valued constraints  BibTeX data for Binarisation via dualisation for valued constraints  Link to Binarisation via dualisation for valued constraints

Tractable Classes of Binary CSPs Defined by Excluded Topological Minors
David A. Cohen‚ Martin C. Cooper‚ Peter Jeavons and Stanislav Živný
In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15). Pages 1945–1951. AAAI Press. 2015.
Details about Tractable Classes of Binary CSPs Defined by Excluded Topological Minors  BibTeX data for Tractable Classes of Binary CSPs Defined by Excluded Topological Minors  Download (pdf) of Tractable Classes of Binary CSPs Defined by Excluded Topological Minors