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:
- 2022 written examination with solution
- 2021 written examination with solution
- 2020 online examination
- 2019 written examination part 1 with solutions, part 2 with solutions
- 2018 written examination part 1 with solutions, part 2 with solutions.
Previous year 2022-2023 based on MiniZInc+Python
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.
- Partial lecture notes
- Yet the following book can be consulted for particular questions on the subject: Handbook of constraint programming