Constraint Solving

Covers state-of-the-art algorithms used in practice to solve combinatorial optimisation problems, focusing on (Max)SAT and (lazy clause generation) constraint programming. The course offers an in-depth view of the algorithms including advanced techniques (e.g., propagator design, conflict analysis, decomposition approaches), alongside techniques that can certify the correctness of the output of the algorithms beyond reasonable doubt. The assignments include a notable programming component with Rust as the programming language. After the course, students will have a principled understanding of the algorithms and will be able to use that knowledge to design their own tailored approaches to solve combinatorial optimisation problems.

The final grade of the course consists of the following components:

• Written Exam (weighting 60%)

• Group Assignment 1: lab assignment (weighting 10%)

• Group Assignment 2: lab assignment (weighting 10%)

• Group Assignment 3: lab assignment (weighting 10%)

• Group Assignment 4: lab assignment (weighting 10%)

Final grade calculation = 0.6 * Written Exam + 0.1 * Group Assignment 1 + 0.1 * Group Assignment 2 + 0.1 * Group Assignment 3 + 0.1 * Group Assignment 4

A passing final grade for the course can only be earned when for all components at least a 5.0 is earned, and the weighted final grade is at least a 5.8.

In case of an insufficient final result, repair options may exist in accordance with Article 17A, Times and number of examinations, sub 1, of the Teaching and Examination Regulations, for:

• Written Exam: Resit opportunity

• Group Assignment 1: Repair opportunity

• Group Assignment 2: Repair opportunity

• Group Assignment 3: Repair opportunity

• Group Assignment 4: Repair opportunity

Disclaimer: information may change depending on unforeseen circumstances or measures (see: TER Art 2, sub 5).