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 its different back end constraint solvers (SAT, FD, LP, MILP, CMA-ES) will be used as unifying framework and as basis for showing the practical complexity of different solvers on some NP hard problems.


• Introduction to AI algorithms for automated reasoning and search

        → TP Constraint modeling language MiniZinc and puzzle solving

• Boolean satisfiability, SAT solvers

        → TP MiniZinc-SAT on graph coloring and graph morphism problems

• Polynomial complexity classes, phase transition phenomena

        → TP MiniZinc-SAT on random clauses

• Finite domain constraints, domain filtering algorithms, branch and bound

        → TP MiniZinc-FD on job-shop scheduling

• Complete, heuristic and local search procedures

        → TP MiniZinc-FD on job-shop planning

• Symmetry breaking constraints

        → TP MiniZinc-FD on the social golfer problem

• Global constraints

        → TP MiniZinc-FD on cumulative constraint

• Linear programming

        → TP MiniZinc-MILP on traveling salesman problems

• Black box continuous optimization

        → TP MiniZinc-CMA-ES on geometrical placement problems

Modalités d'évaluation : Oral + soutenance de mini projet

Langue du cours : Anglais & Français

Credits ECTS : 4