Entry requirements

120 credits. The students must be able to define (or independently learn) basic concepts in algebra, combinatorics, logic, graph theory, and set theory. They must be able to implement (basic) search algorithms. This corresponds to parts of the courses Basic course in Mathematics, Algebra I, 10 credits in programming.

Learning outcomes

In order to pass, the student must be able to

• describe and prove the basic underlying concepts of constraint programming.
• describe how a generic constraint solver works, by giving its architecture and explaining the principles it is based on.
• model a combinatorial problem as a so-called constraint program, using the primitive constraints of a given so-called constraint solver.
• devise (empirically) a suitable heuristic control of the search that is to be performed by the constraint program.
• formulate and compare (empirically) several alternative constraint programs for the same combinatorial problem.
• evaluate (empirically) the computational consequences of having a controlled redundancy among the variables or among the constraints.
• identify and break (some of the) symmetries in a constraint program for a combinatorial problem, thereby speeding up its execution.
• enhance a given constraint solver with an additional constraint, by devising a filtering algorithm for it, and argue why it is faster than its reformulation based on the existing constraints of the solver.
• describe briefly some other technologies for modelling and solving combinatorial problems, such as integer linear programming and local search.

Content

The aim in a combinatorial problem is to make decisions about the values of some variables such that some constraints on these variables are satisfied. Optionally, some expression on these variables must furthermore take a maximal or minimal value. The number of candidate decision combinations is usually astronomical, so that overly naive search or just fast computers are of little help. The efficient solution of combinatorial problems is crucial in many real-life application domains, such as configuration, design, logistics, planning, scheduling, transportation, the natural sciences, and so on.

The course covers:

The basic concepts of constraint programming.

Modelling combinatorial problems in terms of constraints.

Constraint consistency and propagation.

Global constraints and their propagation algorithms.

Search: construction of the search tree, exploration of the search tree, heuristics.

Constraint-based local search.

Constraint-based scheduling.

Optimisation.

Advanced techniques: set variables, dealing with redundancy and symmetry.

Alternative technologies: local search, integer programming, boolean satisfiability, etc.

Implementation in a constraint programming language.

Instruction

Lectures, guest lectures, laboratory work, lessons, optional assignments, and a mandatory project.

Assessment

Exam at the end of the course (5 HEc).

Written project report at the end of the course (3 HEc).

Assignments during the course (2 HEc).