What CP is, the three parts of a constraint satisfaction problem, and a first model in MiniZinc.
Constraint Programming
Describe the problem, not the solution. Learn to model scheduling, timetabling and configuration problems and let a solver find the answers, in MiniZinc and in Python with OR-Tools.
Intermediate
A different way to solve hard problems
In constraint programming you state what a solution must satisfy: variables, the values they can take, and the rules between them. A solver then reasons about the rules and searches for solutions. You will learn to write good models and to understand what the solver does with them, so you can tell why one model runs in seconds and another never finishes.
- Prerequisites: basic programming and secondary-school algebra
- Every unit mixes explanation, worked examples and hands-on labs
- Classic puzzles first, then real scheduling and resource problems
- Finish with a capstone on a real problem of your choice
10
Units
12
Weeks
3 hours a week
36
Hours
in total
1
Capstone
a real problem
The 10 units
Unit 1
Introduction to constraint programming
Unit 2
Modelling with variables, domains and constraints
Integer, boolean and set variables, reified constraints, arrays and data files.
Unit 3
Global constraints
all_different, element, table, count, cumulative, circuit and regular, and why one global constraint beats many small ones.
Unit 4
Constraint propagation and consistency
How a solver rules values out before searching: arc consistency, bounds consistency and the fixpoint.
Unit 5
Search
Backtracking, variable and value ordering, restarts and search annotations, with their effect measured.
Unit 6
Optimisation with constraints
Objectives, branch and bound, proofs of optimality and time limits.
Unit 7
Better models
Symmetry breaking, redundant constraints, channelling and reformulation.
Unit 8
Scheduling and resource problems
Cumulative and disjunctive constraints, job-shop scheduling and a small timetabling model.
Unit 9
CP-SAT and hybrid methods
Lazy clause generation, OR-Tools CP-SAT from Python, large neighbourhood search, and CP with MIP.
Unit 10
Capstone: model a real problem
Rostering, timetabling, routing or configuration: model it, test it on real data, improve it and present it.
What you will work with
MiniZinc
A modelling language for constraint problems, used throughout the course.
OR-Tools CP-SAT
Google's open-source solver, called from Python in Unit 9 and the capstone.
Classic problems
Map colouring, Sudoku, SEND + MORE = MONEY, job-shop and timetabling.
Questions about this course
Basic programming in any language and secondary-school algebra. You do not need to have studied optimisation before.
MiniZinc and Python with OR-Tools. Both are free. Unit 1 shows you how to set them up.
In blended format: live sessions with a teacher, plus lessons, labs and unit checks on our learning platform. Live sessions are timetabled for each group, and you receive the timetable when you join.
Start dates are set for each group. Sign up or contact us and we will tell you when the next group starts.
Contact us for the current fee and the payment options.