Entry requirements

120 credits including Basic Course in Mathematics, Algebra I, and 10 credits in computer programming or another combination of courses containing basic concepts in algebra, combinatorics, logic, graph theory, set theory and implementation of (basic) search algorithms.

Learning outcomes

In order to pass, the student must be able to

• define the concept of combinatorial (optimisation or satisfaction) problem.
• describe the concept of constraint, as used in constraint programming (CP), and how a CP solver works, by giving its architecture and explaining the principles it is based on.
• model declaratively a combinatorial problem, using the primitive constraints of a CP solver.
• devise (empirically) a search heuristic that can be used by a CP solver.
• formulate and compare (empirically) alternative constraint programs (with model and search parts) for a combinatorial problem.
• change the model, e.g., by introducing controlled redundancy or by detecting and breaking symmetries and evaluate the computational consequences.
• augment a CP solver with a constraint, and evaluate (empirically) whether it is better than a reformulation based on the existing constraints of the solver.
• describe briefly some other combinatorial optimisation technologies and hybrid technologies.
• present and discuss topics related to the course content, orally and in writing, with a skill appropriate for the level of education.

Content

The course focuses on methods for solving optimisation problems. Modelling is only covered briefly.

Combinatorial (optimisation or satisfaction) problems. Constraints and global constraints. Constraint consistency and propagation.

Modelling of combinatorial problems in terms of (global) constraints; reification; redundancy of variables, redundancy of constraints; symmetry in problems, models, and instances; set variables, set constraints. Solving by systematic search: construction and exploration of a search tree; heuristics; handling of an objective function for optimisation. Solving by (constraint-based) stochastic local search: construction and exploration of a search space; heuristics, meta-heuristics. Constraint-based scheduling. Alternative combinatorial problem solving technologies: stochastic local search, integer linear programming, Boolean satisfiability, etc., and hybridisation. Applications and extensions.

Instruction

Lectures, guest lectures, mandatory assignments, a mandatory project, help sessions, and solution sessions.

Assessment

Oral and written presentation of assignments (2 credits) oral and written project presentations (3 credits) written test (5 credits) which, when applicable, is included in the project.