Course handouts INF555 - Constraint-based Modeling and Algorithms for Decision Making Problems (36h)
Modélisation et Algorithmes à base de Contraintes pour les Problèmes d'Aide à la Décision
François Fages, Mathieu Hemery, Inria Saclay Ile de France
Ecole Polytechnique
Master Artificial Intelligence & Advanced Visual Computing
Master of Science and Technology
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 modeling 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 NP hard problems.
Schedule 2022-2023 (see Moodle 2022-2023)
- 21 September Constraint satisfaction problems and the constraint-based modelling language MiniZInc
- TP Puzzle solving in MiniZinc with preliminaries on Python and Jupyter notebooks
- TP Puzzle solving in MiniZinc with preliminaries on Python and Jupyter notebooks
- 28 September Boolean models and SAT solvers
- TP SAT models in MiniZinc and SAT solvers in Python
- TP SAT models in MiniZinc and SAT solvers in Python
- 5 October Computational complexity and phase transition in SAT
- TP random k-SAT problems and graph coloring problems in Python and MiniZinc
- TP random k-SAT problems and graph coloring problems in Python and MiniZinc
- 19 October Constraints over finite domains and domain filtering algorithms
- TP mini FD constraint solver in Python
- TP mini FD constraint solver in Python
- 26 October Search trees and search heuristics
- TP disjunctive scheduling in MiniZinc-FD
- TP disjunctive scheduling in MiniZinc-FD
- 9 November Symmetry breaking constraints
- TP Symmetry breaking in MIniZinc-FD
- TP Symmetry breaking in MIniZinc-FD
- 16 November Global constraints and graph theory
- TP Air Traffic Control in MiniZinc-FD
- TP Air Traffic Control in MiniZinc-FD
- 23 November Arithmetic constraints and linear programming
- TP Linear programming for production planning in MIniZinc-LP
- TP Linear programming for production planning in MIniZinc-LP
- 8 December Constraint-based local search allgorithms
- TP CBLS algorithms in Python
- TP CBLS algorithms in Python
- 14 December: final examination
- The slides of the lectures and the TPs are sufficient to prepare the examination.
- Yet the following book can be consulted on the subject: Handbook of constraint programming
- Previous written examinations