Descriptif

The purpose of this course is to present constraint-based methods used in automated reasoning and search problems. Each lecture of approximatively 2h will be followed by 2h of practical work for illustrating the taught concepts and manipulating the associated tools on decision making applications. 

The constraint modelling language MiniZinc with different back end constraint solvers (SAT, FD, LP) will be used as a unifying framework and as basis for showing the practical complexity of different solvers on some useful NP-hard problems.

• 29 September Constraint satisfaction problems and the constraint-based modelling language MiniZInc
  • TP Puzzle solving in MiniZinc with preliminaries on Python and Jupyter notebooks
• 6 October Boolean satisfiability and SAT solvers
  • TP SAT models in MiniZinc and SAT solvers in Python
• 13 October Computational complexity and phase transition in SAT
  • TP random k-SAT problems and graph coloring problems in Python and MiniZinc
• 20 October Constraints over finite domains and domain filtering algorithms
  • TP mini FD constraint solver in Python
• 3 November Search trees and search heuristics
  • TP disjunctive scheduling in MiniZinc-FD
• 10 November Global constraints
  • TP Air Traffic Control in MiniZinc-FD
• 17 November Symmetry breaking constraints
  • TP Symmetry breaking in MIniZinc-FD
• 24 November Arithmetic constraints
  • TP Linear programming for production planning in MIniZinc-LP
• 8 December Constraint-based local search
  • TP simulated annealing
• 15 December: final examination

Modalités d'évaluation : TPs + écrit final

Langue du cours : Anglais 

Credits ECTS : 4