University of Oxford Logo University of OxfordDepartment of Computer Science - Home

Constraints Research Group - Home

Contents

Group photo

Motivation

Computational problems from many different application areas can be seen as constraint satisfaction problems. For example, the problems of scheduling a collection of tasks, or laying out a silicon chip, or interpreting a visual image, can all be seen in this way. In any constraint satisfaction problem there is a collection of variables which all have to be assigned values, subject to specified constraints. Because of the importance of these problems in so many different fields, new programming languages are being developed to tackle problems of this kind, and there is an annual international conference on Constraint Programming.

Outline of Research

The Constraints Group is a joint research group between Oxford and Royal Holloway, University of London, and is led by Professor Peter Jeavons and Professor David Cohen. We have been studying constraint satisfaction problems since 1989, supported by many sponsors. Amongst these are the EPSRC, the DTI, the Royal Society, the British Council, Vodafone UK Ltd, the Nuffield Foundation. and the (now defunct) UK Radiocommunications Agency.

In all our research we aim to achieve new insights by understanding and reasoning about the abstract structure of the problems we are dealing with. This approach has led to a number of significant advances in the field. For example, we have identified a wide variety of conditions which make particular types of constraint satisfaction problem easy to solve. This work is important theoretically, because it sheds new light on the complexity of some classical computational problems. It is also important in practice, because it leads to the design of more efficient algorithms for many types of problem.

MathsCSP Logo Together with Andrei Krokhin we organised an international workshop in Oxford on the Mathematics of Constraint Satisfaction as part of the Logic and Algorithms programme at the Isaac Newton Institute. The web-site for this workshop has lecture slides for the tutorials and other talks given at the workshop, as well as a list of open problems. This workshop inspired a series of workshops on mathematical aspects of Constraint Satisfaction including Dagstuhl (2006), Nashville (2007), Szeged (2007), Palo Alto (2008), Edinburgh (2008), Dagstuhl (2009), Cambridge (2010), Toronto (2011), Dagstuhl (2012), and Banff (2014).


Current Research

Our theoretical research is currently focussed on the following problems:

On the applications side we are particularly interested in the following problems:

Members of the Group

Former Members of the Group

Recent publications produced by members of the Constraints Group are available online.

This site also contains information about current and recent research grants and software developed by members of the Constraints Group.

For a list of useful links, see here.