Objectif :
Ce cours propose une introduction à la recherche opérationnelle et à l'aide à la décision. Il s'appuie sur deux problèmes liés à l'agrégation de relations binaires. Le premier, issu de la théorie du vote, consiste à savoir comment traduire un ensemble de préférences individuelles en une préférence collective qui reflète le mieux possible ces préférences individuelles ; le second, relevant du domaine de la classification, consiste à savoir comment regrouper des entités en classes telles que deux entités d'une même classe paraissent semblables (par rapport à un ensemble de critères fixés) et, au contraire, pour que deux entités de deux classes différentes apparaissent comme dissemblables.

Pendant cette semaine, on modélisera mathématiquement ces problèmes d'agrégation à l'aide de graphes ou sous la forme d'un problème de programmation linéaire en 0/1. On étudiera ensuite sa complexité. Puis on décrira différentes méthodes d'optimisation combinatoire permettant de résoudre ces problèmes de manière exacte ou approchée. Certaines de ces méthodes seront programmées, en C et en Java, pendant des séances de travaux pratiques. Un écrit et ces TP constitueront le contrôle de connaissances.

Descriptif :
Les différentes séances du cours seront consacrées aux thèmes suivants.
- Introduction à la recherche opérationnelle et à l'aide à la décision
- Méthodes d'aide à la décision multicritère
- Illustrations de paradoxes en théorie du vote
- Modélisations mathématiques de l'agrégation de préférences ou de relations d'équivalence à l'aide de graphes ou sous forme de problèmes de programmation linéaire en 0/1
- Méthodes exactes ou approchées d'optimisation combinatoire appliquées aux problèmes précédents : heuristiques et métaheuristiques, relaxation lagrangienne, méthodes arborescentes par séparation et évaluation
- Des TP de programmation en C et en Java permettront d'illustrer certaines des méthodes précédentes aux problèmes décrits plus haut.