Constraints Research Group - Home

Contents

• Motivation
• Outline of Research
• Members of the Group
• Group Publications
• Grants
• Software
• Other Constraints Sites

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.

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), Toronto (2011), Dagstuhl (2012), Melbourne (2013), Banff (2014), Dagstuhl (2015), Berkeley (2016), Nashville (2016), Berkeley (2016), Dagstuhl (2018), Oberwolfach (2021), and Durham (2021).

Current Research

Our theoretical research is currently focussed on the following problems:

• Computational Complexity
  Problems with constraints are generally hard to solve efficiently, but we have shown that mathematical properties of the constraints can be used to identify special classes that are easier to solve. This work makes use of tools from algebra, logic and graph theory.
• Soft Constraints
  Many problems are better modelled with soft constraints, which allow different levels of desirability to be associated with different combinations of values. We are developing new mathematical tools to study the computational complexity and expressive power of soft constraints.
• Groebner Bases
  Mathematicians have developed some powerful techniques for solving polynomial equations, including the idea of reducing a set of equations to a simpler form, called a Groebner basis. We have investigated whether these techniques can be adapted to solve constraint problems more efficiently.

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

• Configuration
  Many commercial organisations are faced with configuration problems, where the task is to find a suitable combination of products that will meet a customer's requirements. Such problems can be modelled as constraint satisfaction problems, often with additional optimisation requirements, and we have investigated the best mathematical and computational frameworks to express and solve such problems effectively.
• Computational Molecular Biology
  A wide variety of new computational problems are arising in molecular biology. For example, the enormous growth in sequence data, from the human genome project and similar sequencing projects for other species, has resulted in an urgent need for effective algorithms which can process this data and extract useful biological information. W-e are looking at ways in which constraints can be used to specify relevant properties of sequences, and constraint programming techniques can be used to search efficiently in very large datasets.
• Scheduling
  Large scale scheduling problems, such as the planning of manufacturing processes, or the design of airline timetables are notoriously difficult to solve. In these problems we have to find an assignment of times to activities subject to constraints which say that one activity must precede another, or that one activity must not overlap with another, and so on. By restricting the problem a little, it is possible to ensure that it can be solved efficiently, but it may not be possible to express the real-world situation. We have been studying the possible restrictions on scheduling problems and how they affect computational complexity.
• Radio Frequency Planning
  The growth of mobile telecommunications means that there is a rapidly increasing demand for use of the radio frequency spectrum. Since there is only a limited amount of radio spectrum available for use, it is important to manage it efficiently. A few years ago we investigated how to best model this problem as a constraint satisfaction problem, and how to apply constraints techniques to solve it.

Members of the Group

• Peter Jeavons
• David Cohen (Royal Holloway)
• Leslie Goldberg
• Georg Gottlob
• Standa Živný

Former Members of the Group

• Markus Aschinger (now at Satalia)
• Andrei Bulatov (now at Simon Fraser University, Canada)
• Clément Carbonnel (now at LIRMM)
• Páidí Creed (now at Benevolent AI)
• Conrad Drescher (now at SAP)
• Peter Fulla (now at NII)
• Richard Gault (who went on to Tessella)
• Martin Green
• Sumedha Gunewardena (now at University of Kansas Medical Center, USA)
• Chris Jefferson (now at University of St Andrews)
• Andrei Krokhin (now at University of Durham)
• Justyna Petke (now at University College London)
• Karen Petrie (now at University of Dundee)
• Miguel Romero (now at Adolfo Ibañez University)
• András Salamon (now at University of St Andrews)
• Evgenij Thorstensen (now at Planixs)

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.