Course handouts CSC_51055_EP - Symbolic AI with Constraint Logic Programming (36h)

IA formelle 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

2025-2026

Description

This course presents Symbolic Artificial Intelligence methods based on the modeling of the problem to solve by mathematical variables, constraints and logical formulae, and its solving using general purpose constraint solvers and logical resolution principles.

Each session is composed of a 2h lecture and 2h programming work (TD) 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 TDs to learn to solve questions of knowledge representation, deductive databases, symbolic computation, constraint solving, search algorithms, solving of combinatorial optimization problems, ressource allocation, placement, planning and task scheduling for decision support.

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, plus possibly a bonus for late answers provided after the TD).

Schedule TBA

Introduction to Constraint Logic Programming

TD Knowledge representation in Datalog with constraints

First-order terms and predicate logic

TD Symbolic computation on lists and arrays in Prolog

Domain filtering and constraint propagation algorithm

TD programming in Prolog of a constraint solver over the integers

Search procedures and heuristics

TD Comparing heuristics, 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-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 5 over 6 TPs
  • 50% final written examination.

Bibliography:

Schedule 2024-2025

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)