IP5003 - Constraint programming

Objectives

General objective:

Model and solve combinatorial optimisation problems with Constraint Programming.

Detailed objectives:

Understand the Constraint Satisfaction Problem (CSP) formalism and how it can be used to model combinatorial optimisation problems.
Understand constraint propagation and be able to enforce arc-consistency on a CSP.
Understand Branch & Prune and Branch & Bound algorithms, as well as search strategy issues.
Master the basic concepts (domains, unknowns, global constraints, search goals) of a non-Prolog Constraint Programming (CP) library.
Model and solve combinatorial optimisation problems with CP.
Experiment with search strategies.
Understand the interest of symmetry breaking and redundant constraints.

Position in the programme

Must be scheduled after Logic Programming. Require basic knowledge in functional programming (OCaml).

Hours

• Lecture : 10h
• Labs work : 12h

Form of assessment

Total assessment hours: 2