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

• define the concept of combinatorial (optimisation or satisfaction) problem.
• describe the concept of constraint, as used in constraint programming (CP).
• describe 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.
• evaluate (empirically) the computational consequences of having a controlled redundancy among the decision variables or among the constraints in the model.
• detect and break (some of the) symmetries in a model for a combinatorial problem, thereby speeding up its solution.
• 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

In a combinatorial optimisation problem, the aim is to find values in the given discrete domains of decision variables such that given constraints on these variables are satisfied and a given objective function on these variables takes a minimal (or maximal) value. These problems are often NP-hard, so that overly naive search or just fast computers are of little help. The efficient solution of combinatorial problems is increasingly crucial in many real-life application domains, such as resource allocation, personnel planning, scheduling, transportation logistics, configuration, design, the natural sciences, finance, and so on.

The course covers:

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 assignment presentations 2 credits, oral and written project presentations 3 credits, assignment and project bonus and written exam 5 credits.