- Department: Computer Science
- Credit value: 10 credits
- Credit level: M
- Academic year of delivery: 2022-23
Constraint programming is a collection of techniques for solving discrete optimisation problems. The module will introduce constraint solving techniques and algorithms, and will teach how to model (represent) and solve discrete optimisation problems with constraints.
Occurrence | Teaching period |
---|---|
A | Autumn Term 2022-23 |
Constraint programming is a collection of techniques for solving discrete optimisation problems. In general, discrete optimisation problems have a set of decisions that must be made (for example, to decide on the start times of tasks in a project scheduling problem). Usually the decisions have to satisfy some hard constraints (e.g. two tasks that use the same machine can't overlap). Also there is often some criteria to optimise: for example, the total length of time to complete all tasks. Examples of discrete optimisation include problems in timetabling, scheduling, allocation, planning, configuration, layout and routing.
The module will introduce constraint solving techniques and algorithms, and will teach how to model (represent) and solve discrete optimisation problems using constraint programming. The aims of the module are to give students practical skills in modelling and solving difficult problems, and the necessary background knowledge of how constraint solvers work.
On successful completion of the module, students should be able to:
The main content of the module will be in two parts of approximately equal size. The first part is about modelling (representing) discrete optimisation problems using a constraint modelling language. We will look at common modelling patterns for representing structures such as sets, multisets and variable-length sequences, and how to combine these patterns. We will also look at some more advanced modelling techniques such as how to remove symmetries from a model to improve its performance. The second part of the module is about algorithms and heuristics for solving constraint problems. We will look at search algorithms and also reasoning algorithms that help to reduce the amount of search that is needed in modern constraint solvers.
Task | % of module mark |
---|---|
Essay/coursework | 100 |
None
Task | % of module mark |
---|---|
Essay/coursework | 100 |
Individual written feedback will be provided for the practical assessment. In lab sessions we will go through solutions to the set problems, providing feedback to the whole class. Individual feedback will also be available in the lab sessions.
** Russell, S. and P. Norvig, Artificial Intelligence: A Modern Approach, Pearson, 3rd edition, 2013
** K. Apt, Principles of Constraint Programming, Cambridge University Press, 2003.