Course Catalogue

View Specification Document | Reading List

We cover Constraint Programming and its use in solving a number of combinatorial problems. We also cover the underlying technology, and related combinatorial optimisation approaches.

3 hours per week

For MSc students - Honours degree in Computing Science
For Honours students - 3rd year Computing Science
For MSci students - 4th year Computing Science

None

None

Summative coursework will consist of multiple-choice quizzes (20% within the 'set exercise' category), set coding tasks with descriptions of results (30% within the 'set exercise' category), and a research-focussed project output (e.g. a research-style poster).

Reassessments are normally available for all courses, except those which contribute to the Honours classification. For non Honours courses, students are offered reassessment in all or any of the components of assessment if the satisfactory (threshold) grade for the overall course is not achieved at the first attempt. This is normally grade D3 for undergraduate students and grade C3 for postgraduate students. Exceptionally it may not be possible to offer reassessment of some coursework items, in which case the mark achieved at the first attempt will be counted towards the final course grade. Any such exceptions for this course are described below. 

The coursework cannot be redone because the nature of the coursework is such that it takes a significant number of days to produce it and this effort is infeasible for supporting the re-doing of such coursework over the summer.

To enable students to implement constraint programming solutions to a number of combinatorial problems using a state of the art constraint programming toolkit.
To give students a critical appreciation of the fundamental concepts of constraint satisfaction and constraint programming, and the ability to compare to related search approaches.
To give the student an appreciation of, and exposure to, commercial applications and the research directions in constraint programming.
To understand the basic mechanics of a constraint programming toolkit (such that they might implement such a toolkit).

By the end of this course students will be able to:

1: Model complex problems (such as scheduling problems, design and configuration problems) as constraint programs, using a state of the art constraint programming toolkit;

2: Implement the algorithms for achieving constraint propagation, and critically appreciate the costs and benefits of different levels of consistency;

3: Demonstrate extensive, detailed and critical knowledge and understanding of constraint satisfaction from a theoretical point of view, and be able to compare to other combinatorial approaches;

4: Implement, the search algorithms typically used in constraint programming;

5: Use various variable and value ordering heuristics;

6: Discuss current issues and research direction in constraint programming.

Students must submit at least 75% by weight of the components (including examinations) of the course's summative assessment.