Accessibility statement

Constraint Programming - COM00159M

« Back to module search

  • Department: Computer Science
  • Module co-ordinator: Dr. Peter Nightingale
  • Credit value: 10 credits
  • Credit level: M
  • Academic year of delivery: 2022-23
    • See module specification for other years: 2021-22

Module summary

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.

Module will run

Occurrence Teaching period
A Autumn Term 2022-23

Module aims

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.

Module learning outcomes

On successful completion of the module, students should be able to:

  • Identify the algorithms used in modern constraint solvers and execute them on small examples;
  • Construct a simple constraint solver;
  • Model (represent) and solve discrete optimisation problems using a modern constraint programming system;
  • Analyse the performance of a constraint solver on simple constraint models.

Module content

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.

Assessment

Task Length % of module mark
Essay/coursework
Constraint Modelling & Solving		 N/A 100

Special assessment rules

None

Reassessment

Task Length % of module mark
Essay/coursework
Constraint Modelling & Solving		 N/A 100

Module feedback

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.

Indicative reading

** Russell, S. and P. Norvig, Artificial Intelligence: A Modern Approach, Pearson, 3rd edition, 2013

** K. Apt, Principles of Constraint Programming, Cambridge University Press, 2003.


The information on this page is indicative of the module that is currently on offer. The University is constantly exploring ways to enhance and improve its degree programmes and therefore reserves the right to make variations to the content and method of delivery of modules, and to discontinue modules, if such action is reasonably considered to be necessary by the University. Where appropriate, the University will notify and consult with affected students in advance about any changes that are required in line with the University's policy on the Approval of Modifications to Existing Taught Programmes of Study.