Module Details

CE884-7-SP-CO: Constraint Satisfaction For Decision Making

Note: This module is inactive. Visit the Module Directory to view modules and variants offered during the current academic year.

Year: 2016/17
Department: Computer Science and Electronic Engineering
Essex credit: 15
ECTS credit: 7.5
Available to Study Abroad / Exchange Students: Yes
Full Year Module Available to Study Abroad / Exchange Students for a Single Term: No
Outside Option: No
Comments: Pre-Requisite - Knowledge of data structure and programming in a high level language Knowledge of heuristic search and optimization are preferred but not necessary.

Supervisor: Professor Edward Tsang
Teaching Staff: Professor Edward Tsang
Contact details: School Office, csee-schooloffice (non-Essex users should add to create full e-mail address), Telephone 01206 872770

Module is taught during the following terms
Autumn Spring Summer

Module Description

Learning Outcomes

The aim of this module is to provide students with an understanding of constraint satisfaction and optimisation techniques and their applications.

After completing this module, students will be expected to be able to:

1. Assess whether a given problem can be formulated as a constraint satisfaction problem.
2. Formulate constraint satisfaction problems.
3. Demonstrate an understanding of the basic techniques for solving constraint satisfaction problems.
4. Apply constraint satisfaction techniques to solve constraint satisfaction problems.
5. Implement basic constraint satisfaction and optimisation algorithms.
6. Appreciate applications of constraint technology.

Outline Syllabus

This module will cover fundamental concepts as well as practical algorithms in constraint satisfaction. In particular, it will cover:

Basic concepts in constraint satisfaction problems
. Problem reduction concepts and problem reduction algorithms
. Systematic search algorithms for constraint satisfaction
. Constrained optimisation problems
. Stochastic search methods, including hill climbing and Guided Local Search for constraint satisfaction and optimisation
. Frontier research in constraint satisfaction and optimisation.

Case studies (including an assignment) will be used to show students how to formulate constraint satisfaction and optimisation problems and how to choose among different models. Industrial talks will be arranged to expose students to industrial applications of constraint technology.

Learning and Teaching Methods

Class and Lectures


20 per cent Coursework Mark, 80 per cent Exam Mark


Coursework % wk submitted Assignment 1 10% 21 Assignment 2 10% 25

Other information



  • Recommended Reading
  • TSANG, E.P.K., Foundations of Constraint Satisfaction, Academic Press, 1993
  • ROSSI, F., van BEEK P. & WALSH T. (editors), Handbook of Constraint Programming, Elsevier, 2006