Course handouts INF555 - Constraint-based Modeling and Algorithms for Decision Making (36h)
Modèles et Algorithmes à base de Contraintes pour l'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
2023-2024
The purpose of this course is to present constraint-based methods for mathematical modeling and computational solving of combinatorial search problems, with applications especially in industry and life sciences.
Each lecture of approximatively 2h will be followed by 2h of practical work for illustrating the taught concepts and manipulating the associated tools.
The logic programming language SWI-Prolog with its constraint solving libraries (clpfd.pl
, clpr.pl
) and a constraint-based modeling library (microzinc.pl
inspired by the MiniZinc modeling language)
will be used as a unifying framework for both the mathematical modeling of decision making problems and the programming of constraint solvers, and for showing the practical
complexity of different models and different solvers on some NP hard problems.
Schedule 2023-2024 (see also Moodle 2023-2024)
- 20 September Introduction to Constraint Logic Programming
- TD Datalog with constraints
- TD Datalog with constraints
- 27 September First-order predicate logic and equality on terms
- TD Symbolic computation and lists in Prolog
- TD Symbolic computation and lists in Prolog
- 4 October Constraint solving by domain filtering
- TD programming a CLP(Z) constraint solver over the integers in Prolog
- TD programming a CLP(Z) constraint solver over the integers in Prolog
- 11 October Search procedures and heuristics
- TD Comparing heuristics, disjunctive scheduling
- TD Comparing heuristics, disjunctive scheduling
- 18 October Symmetry breaking constraints
- TD Graph colouring and symetries in the Nqueens placement problem
- TD Graph colouring and symetries in the Nqueens placement problem
- 25 October Constraints over the real numbers in CLP(R)
- TD Production planning and cost-benefit analysis
- TD Production planning and cost-benefit analysis
- 8 November Boolean models and SAT solvers
- TD Programming a SAT solver in Prolog
- TD Programming a SAT solver in Prolog
- 15 November NP-completeness and phase transitions
- TD random k-SAT problems and random graph coloring
- TD random k-SAT problems and random graph coloring
- 22 November Constraint-based local search algorithms
- TD Constraint-based hill-climbing, simùulated annealing, tabu search.
- TD Constraint-based hill-climbing, simùulated annealing, tabu search.
- 20 December: final examination
- The slides of the lectures and the TDs are sufficient to prepare the examination.
- Lecture notes
- Yet the following book can be consulted for particular questions on the subject: Handbook of constraint programming
Previous written examinations
In previous years the modeling language MiniZinc and programming language Python were used in place of the single declarative programming/modeling language Prolog for this course: