Prescriptive Analytics

Objectifs

This course addresses several efficient models for processing data encountered in industrial combinatorial problems. These models are based on logical inference and mathematical optimisation techniques : constraint satisfaction problems (CSPs), boolean satisfiability (SAT)
and integer linear programming (ILP).
In the first part (CSPs), students are expected to understand and to be able to apply the main constraint propagation techniques and solving strategies, by hand, but are also initiated to programming tools that integrate general solvers (ex : CPLEX) during practical works.
In the SAT modeling part of this course, students are initiated to some propagation and heuristic solving techniques used in SAT solvers (DPPLL, Implication Graphs, Conflict Analysis, Two-watched litterals algorithm). Various applications problems such as allocation, graph colouring, scheduling serve as training examples for SAT encoding.
In the last part (MILPs), students will have to translate industrial problems into mixed-integer linear programs, then to solve them efficiently using branching algorithms or decomposition methods, embedded in existing tools such as CPLEX.

Pré-requis

Algorithmics & programming (I2MIIF11, I2MIIF21).
Fundamentals in Computer Science (I4IRIF11), Intelligent
Systems (I4IRSD11)

Évaluation

L’évaluation des acquis d’apprentissage est réalisée en continu tout le long du semestre. En fonction des enseignements, elle peut prendre différentes formes : examen écrit, oral, compte-rendu, rapport écrit, évaluation par les pairs…