Course handouts CSC_51055_EP - Constraint-based Models and Algorithms for Decision Support (36h)
IA symbolique en programmation logique avec contraintes
François Fages, Mathieu Hemery, Inria Saclay Ile de France
Ecole Polytechnique
Master Artificial Intelligence & Advanced Visual Computing
Master of Science and Technology
2026-2027
Description
This course presents symbolic AI problem solving methods based on a modeling of the problem to solve by mathematical variables, constraints, logical formulae, and their resolution by the recourse to general-purpose constraint solving algorithms, logical deduction and heuristic search procedures.
Each session is composed of a 2h lecture and 2h practice tutorial (TP) for experimenting the taught concepts of Constraint Logic Programming. You will use the system SWI-Prolog with its libraries for constraint solving and constraint-based modeling in a series of 9 TPs to learn to solve questions of knowledge representation, deductive databases, symbolic computation, constraint solving, search algorithms, solving of combinatorial optimization, ressource allocation, placement, planning and task scheduling problems for decision support in industry.
Grading
50% written examination,
50% mean of the 7 best grades given to the 9 TDs (the TD grade is based on the file uploaded at the end of the 2h TD session, after what a solution is provided).
Schedule TBA
- Introduction to Constraint Logic Programming, term unification
- TD Deductive databases, symbolic computation
- Operational semantics of CLP(X) languages, proving programs correct
- TD navigation in a map
- Domain filtering and constraint propagation algorithm
- TD programming of a constraint solver for interval arithmetic
- Search procedures and heuristics
- TD disjunctive scheduling
- Symmetry breaking constraints
- TD Graph colouring, symmetry breaking in placement problems
- Constraints over the real numbers in CLP(R)
- TD Production planning and cost-benefit analysis
- Boolean models and SAT solvers
- TD Programming a SAT solver in Prolog
- NP-completeness and phase transitions
- TD random k-SAT problems and random graph coloring
- Constraint-based local search
- TD Constraint-based hill-climbing, simulated annealing, tabu search.
Final examination
Previous written examinations
- 2024 written examination with solution
- 2023 written examination with solution
- 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.
2024-2025
Course handouts CSC_51055_EP - Constraint-based Modeling and Algorithms for Decision Support (36h)
Modèles et Algorithmes à base de Contraintes pour l'Aide à la Décision
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 (modeling.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.
Grades:
- 50% mean of your best 7 over 9 TPs
- 50% final written examination.
Bibliography:
- mini manual of SWI-Prolog including pointers to pack modeling
- The lecture notes, plus slides of the lectures and solutions of the TDs are sufficient to prepare the examination.
- Yet the Handbook of Constraint Programming can be consulted for further questions on the subject.
Schedule 2024-2025
- 25 September Constraint satisfaction problem modeling and solving with general purpose constraint solvers
- TD Solving puzzles in SWI-Prolog with modeling pack
- TD Solving puzzles in SWI-Prolog with modeling pack
- 2 October The class of constraint programming languages CLP(X)
- TD Deductive databases, knowledge graphs
- TD Deductive databases, knowledge graphs
- 9 October CLP(H) on the Herbrand's domain of first-order logic terms
- TD symbolic differentiation, list processing, task scheduling
- TD symbolic differentiation, list processing, task scheduling
- 23 October CLP(Z) domain filtering algorithms
- TD Programming a constraint solver for task scheduling problems
- TD Programming a constraint solver for task scheduling problems
- 6 November Complexity classes, search procedures and heuristics
- TD Heuristics in the N-queens problem. Solving an NP-hard disjunctive task scheduling problem for building a bridge.
- TD Heuristics in the N-queens problem. Solving an NP-hard disjunctive task scheduling problem for building a bridge.
- 13 November Symmetry breaking constraints
- TD Symmetry breaking in the N-queens problem. Automated theorem proving in group theory
- TD Symmetry breaking in the N-queens problem. Automated theorem proving in group theory
- 20 November CLP(R) linear programming, Fourier's elimination alg.
- TD Programming a SAT solver in Prolog
- TD Programming a SAT solver in Prolog
- 4 December Boolean modeling, SAT solvers, NP-completeness
- TD Tracing a SAT solver, observing phase transition in random 3-SAT
- TD Tracing a SAT solver, observing phase transition in random 3-SAT
- 11 December 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.
- 18 December: final examination
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.
- Yet the following book can be consulted for particular questions on the subject: Handbook of constraint programming