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 Max-CSP) 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 Max-CSP are NP-hard, 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.