The Constraints Modelling Project
University of Essex

Researchers involved:
Edward Tsang, James Borrett

This project started in around 1990 when Tsang looked at the role of problem formulation (now commonly called medelling) in constraint satisfaction. The usefulness of modelling in problem solving is not new. It is considered more an art than science, which is absolutely true. Tsang argued that modelling in constraint satisfaction is more manageable than modelling in general because a constraint satisfaction problem is defined by nothing but the variables, domains and constraints. A paper was submitted to AI Commummications (European Magazine) in the early 90s, which was rejected with the feedback that "there was not much new".

Borrett started his PhD in modelling in constraint satisfaction in 1994. By setting up a formal framework for defining the problem of model selection and defining criteria for evaluating binary constraint models, Borrett's PhD thesis (1998) made a small but significant start towards constraint modelling. The modelling idea is part of the adaptive constraint solving concept, which was demonstrated by the "Quickest First Principle".

Selected Publications:

Borrett & Tsang 2009

Borrett, J. & Tsang, E.P.K., Adaptive constraint satisfaction: the quickest first principle, in Mumford, C.L. & Lakhmi, J. (ed.), Computational Intelligence: Collaboration, Fusion and Emergence, Intelligent Systems Reference Library, Vol. 1, Springer, 2009, 203-230 (ISBN: 978-3-642-01798-8)
(Early versions: Borrett, J., Tsang, E.P.K. & Walsh, N.R., Adaptive constraint satisfaction: the quickest first principle, Proceedings, 12th European Conference on AI, Budapest, Hungary, 1996, p.160-164
Technical Report CSM-256, Department of Computer Science, University of Essex, November 1995)

Borrett & Tsang 2001 (early version)

J. Borrett, & E.P.K.Tsang, A context for constraint satisfaction problems formulation selection, Constraints, Kluwer Academic Publishers, Vol.6, No.4, 2001, 299-327

Borrett, J.E. (zipped PDF 671K),

Formulation selection for constraint satisfaction problems: a heuristic approach, PhD Thesis, Department of Computer Science, University of Essex, Colchester, UK, 1998

Borrett & Tsang 1995b, CSM-254.ps.Z (47K)

Borrett, J. & Tsang, E.P.K., On the selection of constraint satisfaction problem formulations, Technical Report CSM-254, University of Essex, Colchester, UK, October, 1995

Borrett & Tsang 1996, CSM-264.ps.Z (52K)

Borrett, J. & Tsang, E.P.K., Towards a formal framework for comparing constraint satisfaction problem formulations, Technical Report CSM-264, University of Essex, Colchester, UK, March, 1996

This project is partly funded by EPSRC and University of Essex.