University of York, Department of Computer Science

Implied Constraints Project

[People | FAQ | Publications | Presentations | Links | Contact]

The aim of this project is to develop, analyse and evaluate methods for generating implied constraints automatically. We expect such methods to become a vital component of the next generation of constraint satisfaction toolkits. One of the key ideas will be to combine theorem proving techniques (like proof planning) with constraint satisfaction algorithms. Several recent studies show that implied constraints added by hand to a problem representation can lead to significant reductions in search. There has, however, been little research on how to generate such implied constraints automatically outside of a highly focused domain like planning.

This project ran from October 2000 to October 2003 and was supported by a EPSRC grant (N16192), whose principal investigators were Alan Frisch and Toby Walsh. EPSRC reviewed the results of this project and it was awarded the top rating "Outstanding."