Constraint Programming (CP) is a modeling and solving framework in combinatorial optimization. This course presents the fundamental ideas of CP and its application to scheduling. In particular, the course will go through:

  • Local consistencies as properties of the domains: arc-consistency and bounds-consistency
  • Local consistencies as algorithms: filtering algorithms of global constraints such as Linear (in)equation, AllDifferent, NoOverlap 
  • Modeling with typical constraints (Element, AllDifferent, Global Cardinality, NoOverlap, Cumulative...) and first insights about symmetry breaking and redundant constraints
  • Basic knowledge of tree search, backtracking algorithms and branching heuristics

The course builds upon fundamental techniques of Operations Research such as dynamic programming and graph theory (flow and matching).

Online modeling exercises and quiz have to be completed with a commercial or open-source CP solver to gain a strong and practical modeling skill in CP.

Note: the Caseine course is not (yet) self-contained and is tightly linked to 12h of class sessions and 4h30 of practical sessions