Descriptif

The purpose of this course is to present constraint-based methods used in artificial intelligence and operations research to solve search problems in a variety of application domains. 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-based modelling language MiniZinc with its different back-end constraint solvers (SAT, FD, LP) will be used as a unifying framework to learn how to model a problem with variables and relations, and analyze the practical complexity of different models and solvers on some useful NP-hard problems.

Tentative program:

• C1 Constraint satisfaction problems and introduction to the constraint-based modelling language MiniZInc
  • TD1 Preliminaries on Python and Jupyter notebooks and introduction to MiniZinc on puzzle solving  
• C2 Boolean satisfiability and SAT solvers
  • TD2 SAT models in MiniZinc and SAT solvers in Python
• C3 Computational complexity and phase transition in SAT
  • TD3 random k-SAT problems and graph coloring problems in Python and MiniZinc
• C4 Constraints over finite domains and domain filtering algorithms
  • TD4 mini FD constraint solver in Python
• C5 November Tree search and search heuristics
  • TD5 disjunctive scheduling in MiniZinc-FD
• C6 November Global constraints
  • TD6 Air Traffic Control in MiniZinc-FD
• C7 November Symmetry breaking constraints
  • TD7 Symmetry breaking in MiniZinc-FD
• C8 November Arithmetic constraints
  • TD8 Linear programming for production planning in MIniZinc-LP
• C9 December Constraint-based local search
  • TD9 simulated annealing
• Final examination

Modalités d'évaluation : 50% 6 meilleurs TPs 50% examen 

Langue du cours : documents en anglais, oral en anglais sur demande

Credits ECTS : 4