|
| EPSRC Reference: |
EP/D032636/1 |
| Title: |
Groebner Basis Techniques for Constraint Satisfaction Problems |
| Principal Investigator: |
Professor PG Jeavons |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Computing Laboratory |
| Organisation: |
University of Oxford |
| Scheme: |
Standard Research |
| Starts: |
31 March 2006 |
Ends: |
30 March 2009 |
Value (£): |
167,396
|
| EPSRC Research Topic Classifications: |
| Algebra and Geometry |
Fundamentals of Computing |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
28 Jul 2005
|
Computer Science (Tech) July 05
|
Announced
|
|
|
Summary |
Many of the problems we use computers to solve have the same general form: we want the computer to find values for a collection of variables which satisfy various constraints. The constraints restrict the combinations of values allowed for some subsets of the variables. Many difficult computational problems fit this general framework. For example, the problem of scheduling a collection of building tasks in a sensible order, or putting together a timetable for a school or university. The same kinds of problems arise in choosing the frequencies for mobile phone transmitters, choosing the best routes for a fleet of delivery vehicles, or trying to match a newly-discovered protein structure against a database.
It has turned out to be very useful for some purposes to view all these different problems as basically the same kind of problem: they can all be seen as constraint satisfaction problems. Doing this has led to the development of special programming languages for this kind of problem, and some very general techniques which allow us to analyse such problems and solve them as efficiently as possible.
Some of the most interesting ideas have come from linking problems of this kind to mathematical ideas, such as graph theory, or the idea of an algebra. In this proposal 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.
|
| Final Report Summary |
Many of the problems we use computers to solve have the same general form: we want the computer to find values for a collection of variables which satisfy various constraints. The constraints restrict the combinations of values allowed for some subsets of the variables. Many difficult computational problems fit this general framework. For example, the problem of scheduling a collection of building tasks in a sensible order, or putting together a timetable for a school or university. The same kinds of problems arise in choosing the frequencies for mobile phone transmitters, choosing the best routes for a fleet of delivery vehicles, or trying to match a newly-discovered protein structure against a database.
It has turned out to be very useful for some purposes to view all these different problems as basically the same kind of problem: they can all be seen as constraint satisfaction problems. Doing this has led to the development of special programming languages for this kind of problem, and some very general techniques which allow us to analyse such problems and solve them as efficiently as possible.
Some of the most interesting ideas have come from linking problems of this kind to mathematical ideas, such as graph theory, or the idea of an algebra. In this project we investigated new links 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 explored how these ideas can be used to manipulate constraint satisfaction problems. Also, we investigated ways in which the techniques developed by computer scientists for tackling constraint satisfaction problems and analysing their structure can be used to analyse problems involving polynomials. Bringing the mathematical ideas together with the computational techniques gave us new insights into the mathematical ideas, and suggested some better ways to tackle constraint satisfaction problems. However, we found that techniques for manipulating polynomials are currently far too inefficient to be used effectively in constraint solving (over finite domains). We therefore broadened our investigation to examine representations of constraints as graphs, and used some recent ideas from graph theory (such as the perfect graph theorem, and recent results about hypergraph decomposition) to identify new classes of constraint problems that can be efficiently solved.
|
| Further Information: |
|
| Organisation Website: |
http://www.ox.ac.uk |
|
|