Constraints Research Group - Grants

Home page of the Constraints Group.

• The Complexity of Valued Constraints
  EP/F01161X from EPSRC, for £125,485,396, October 2007 - 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.

• Groebner Basis Techniques for Constraint Satisfaction Problems
  EP/D032636 from EPSRC, for £167,396, April 2006 - March 2009
  In this project we are seeking to build a new link between constraint satisfaction problems and the area of mathematics that deals with polynomial equations. The combinations allowed by a constraint can be represented as the roots of a polynomial equation, and then the solutions that satisfy a whole set of constraints correspond to the roots of a whole collection of polynomial equations. Mathematicians have developed tools for solving polynomial equations, and manipulating them into simpler forms. We want to see how these ideas can be used to manipulate constraint satisfaction problems. Also, we want to see whether the techniques developed by computer scientists for tackling constraint satisfaction problems and analysing their structure can be used in some new ways to analyse problems involving polynomials. We think that bringing the mathematical ideas together with the computational techniques will give us some new insights into the mathematical ideas, and will help to develop better ways to tackle constraint satisfaction problems.

• Tractability of Constraint Problems: Unification, Extension and Applicability
  EP/C525949 from EPSRC, for £184,410, September 2005 - September 2008
  This proposal concerns the broad class of computational problems known as "constraint satisfaction problems". We aim to develop a more powerful and general theory of tractability for these problems which takes into account both the nature of the constraints and the structural properties of the way different constraints interact. This theory will be a major step forward in understanding and exploiting the various different aspects of a constraint problem that can make it feasible to solve. As an application of this new theory we plan to extend existing decomposition methods for these problems by using more sophisticated criteria to identify suitable components. At present, all decomposition methods ignore the nature of the constraints in the components they identify. We expect to be able to identify components of a given problem that are tractable for a variety of different reasons, including the constraint languages used in those components. We believe that we may discover a small number of design patterns describing common properties of many CSP instances, which can be used to guide the choice of solution algorithm. We plan to implement the ideas developed in flexible and robust software tools that can be used by non-specialists to apply the new analysis and decomposition techniques to a wide range of constraint problems.

• Tractable Valued Constraints: An Algebraic Approach
  GR/R81213 from EPSRC, for £5,638, June 2002 - August 2002 , and
  GR/S87454 from EPSRC, for £20,759, June 2004 - June 2006
  This is a collaborative project involving Dr Peter Jeavons at the University of Oxford, Dr David Cohen at Royal Holloway, University of London, and Dr Martin Cooper at the University of Toulouse III, France. The funding is to enable Dr Cooper to visit Dr Jeavons and Dr Cohen for 2 periods of 3 months in 2004 and 2005. Dr Cooper is a specialist in consistency techniques for the family of computational problems known as "constraint satisfaction problems". This family of problems has been widely studied in computer science, and a number of tractable sub-cases of the constraint satisfaction problem have been identified using algebraic techniques. In our initial study we established that similar techniques can be devised to identify tractable cases of the more general "valued constraint satisfaction problem". This is a very general framework which includes many standard forms of optimisation problem, so tractable classes for this problem are of interest for many practical optimisation problems. In this project we aim to obtain a complete description of all the tractable cases for some important special cases of the valued constraint satisfaction problem. We also aim to identify new tractable cases of the general problem and to develop a strong algebraic theory of the complexity of optimisation problems.

• Algebraic Structural Methods and Complexity of Constraint Satisfaction
  GR/R22704 from EPSRC, for £10,170, March 2001 - June 2001, and
  GR/R29598 from EPSRC, for £210,406, May 2001 - August 2004
  These grants enable Dr Bulatov and Dr Krokhin of Ural State University, Russia, to work with Dr Peter Jeavons at the University of Oxford. Dr Bulatov and Dr Krokhin are specialists in algebra, and especially the theory of clones and universal algebra, and these projects are designed to explore how recent results and methods from universal algebra can be linked to the study of the broad family of computational problems known as "constraint satisfaction problems". This family of problems has been widely studied in computer science, and there have been many attempts to characterise restrictions on the general problem which make it possible to solve it efficiently. It appears that considerable further progress with this question could now be made by using structural results from universal algebra, and these projects develop the necessary theory. One novel feature of the approach is that it includes both finite constraint satisfaction problems (such as graph colouring problems, and satisfiability problems) and infinite constraint satisfaction problems (such as temporal and spatial reasoning problems). By taking an abstract, algebraic, approach we plan to develop a framework which naturally incorporates both types of problems (which have traditionally been studied separately) and so obtain a more powerful theory of the computational complexity of these important problems.

• Complexity and Clones - A New Synthesis
  from Oxford University, for £26,175, May 2000-April 2001
  The computational difficulty of solving constraint satisfaction problems places many of them beyond the reach of current, or envisaged, computer technology. The classification of problems according to their degree of difficulty forms the core of computational complexity theory, and has been extensively studied over the last thirty years. The recent discovery by Jeavons of a new, algebraic approach to this classification means that questions about complexity can be transformed into questions about algebraic structure. The search for tractable problem types becomes a search for sets of algebraic invariance properties, or clones. This approach has already yielded new results: Krokhin, Bulatov, and Jeavons have been able to use recent results in universal algebra to identify new tractable problem classes. This grant brings mathematicians and computer scientists together to work on this very novel area at the interface between the two subjects.

• The Algebraic Structure of Complexity Classes
  GR/M12926 from EPSRC, for £106,234, September 1999 - December 2001
  The study of computational complexity theory has recently been transformed by the discovery that there are close connections between the classical complexity classes and various forms of logic. There is considerable interest in this area, which has become known as descriptive complexity theory. The most important discovery arising from this branch of of complexity theory is that most computational complexity classes can be characterised as classes of finite models of sentences in various logics. The present research is prompted by the discovery of a similar relationship between the classical complexity classes and certain algebraic properties. In particular, the complexity of constraint satisfaction problems is determined in many cases by the algebraic closure properties of the relations specified in the problem. We aim to forge novel links between the descriptive view of complexity classes and the algebraic view of those classes. In so doing, we intend to use the techniques and knowledge available in each discipline to advance the state of the art of the other.

• UK Constraint Network: CONSNET
  GR/M66110 from EPSRC, for £40,202, September 1999 - September 2001
  We propose to establish a network of researchers aiming to drive forward the technology and skills available in the UK to tackle computational problems involving constraints. This broad class of problems includes many difficult combinatorial problems arising in a wide variety of industrial and scientific applications. Examples include scheduling, resource allocation, vehicle routing, channel assignment in telecommunications networks, and structure matching in biomolecular databases. The UK has a strong research community in this emerging area, but there has previously been little collaboration between different groups, and no strategic overview of how this technology should be developed. The proposed network will bring together at least eight "active sites" with researchers working in this area, as well as providing a point of contact to enable industrial and other potential end-users to benefit from this expertise. The aims of the network are to increase awareness of the potential of using constraints-based technology, to encourage cross-fertilisation of ideas and new multi-disciplinary research proposals, to publicise and learn from existing successful applications and from problems which are currently out of reach, and to identify and refine the vision of this research community for the long-term future development of constraints technology.

• Improved Modelling and Solution Techniques for the Frequency Assignment Problem
  GR/L06317 from EPSRC, for £52,782, November 1996 - November 1999 (with Vodafone UK Ltd.)
  This research is aimed at the efficient solution of radio coverage problems. That is, we are concerned with finding an assignment of frequencies to radio transmitters in such a way that the "protection ratio"at every point is above an agreed acceptable minimum. (The protection ratio is the ratio of the strength of the desired signal strength to the strength of the unwanted interfering signals.) The radio frequency spectrum is a limited natural resource, so it is of vital economic importance to use information about radio signal propagation more directly to capture the real structure of the frequency restrictions without making unnecessarily conservative assumptions. These general constraints will then be processed and solved using techniques developed for general constraint satisfaction problems.

• Tractability in Constraint Satisfaction Problems with Applications to Frequency Assignment
  GR/L09936 from EPSRC, for £100,408, October 1996 - September 1998
  Many important computational problems may be formulated as "constraint satisfaction problems", and this class of problems has been widely studied. The general form of the problem is computationally intractable, but many recent results have identified sufficient conditions which lead to tractability. This project aims to develop these results further, and to bridge the gap between the theoretical advances and practical applications. The project will therefore focus on a particular type of constraint satisfaction problem, known as the "frequency assignment problem". This problem is of considerable commercial and strategic importance in the areas of telecommunications, but has so far resisted attempts to find effective computational solutions. It therefore provides an ideal testbed for the development of new algorithmic approaches based on structural features. The project will make use of software already developed by the investigators, and a wide variety of realistic problem data provided by the collaborators. The results obtained will therefore be of immediate practical relevance, as well as providing new theoretical insights.