Course code TPT06
Course title Recherche optionnelle et aide à la décision
Institution TELECOM ParisTech
Course address TELECOM ParisTech - 46 rue Barrault - 75013 Paris
City Paris
Minimum year of study 4th year
Minimum level of English None
Minimum level of French Fair
Key words

Recherche opérationnelle, aide à la décision, décision multicritère, théorie du vote, agrégation des préférences, mathématiques sociales, modèles mathématiques, optimisation combinatoire, programmation mathématique

Language French
Professor responsible Prof. Olivier HUDRY
Telephone + 33 (0) 1 45 81 77 63
Fax + 33 (0) 1 45 81 31 19
Email olivier.hudry@telecom-paristech.fr
Participating professors

 

Irène Charon (TELECOM ParisTech, département Informatique et Réseaux)

Olivier Hudry (TELECOM ParisTech, département Informatique et Réseaux)

Number of places Minimum: 10, Maximum: 40, Reserved for local students: 4
Objectives

Ce cours propose une introduction à la recherche opérationnelle (RO) et à l’aide à la décision. On y abordera plusieurs aspects classiques en recherche opérationnelle : des problèmes de référence (problème du voyageur de commerce, problème du sac à dos, un problème de vote), divers types de modélisations (programmation linéaire en variables binaires, graphes), des méthodes générales d’optimisation combinatoire (méthodes arborescentes par séparation et évaluation, programmation dynamique, relaxation lagrangienne, recuit simulé...) permettant de traiter ces problèmes de façon exacte ou approchée.

Plus précisément, on partira d’un problème de vote : comment élire ou classer des candidats à partir des préférences des votants de sorte que cette élection ou ce classement traduisent « le mieux possible » les opinions des votants ? On modélisera mathématiquement ce problème d’agrégation à l’aide de graphes ou sous la forme d’un problème de programmation linéaire en variables binaires. On décrira ensuite des méthodes de résolution issues de l’optimisation combinatoire et applicables à ce problème de vote aussi bien qu’aux autres problèmes classiques mentionnés plus haut. Certaines de ces méthodes feront l’objet d’une programmation en C ou en Java pendant des séances de travaux pratiques.

 

Programme to be followed

-       Introduction à la recherche opérationnelle et à l’aide à la décision

-       Théorie du vote et paradoxes en théorie du vote

-       Modèles mathématiques pour l’agrégation des préférences (graphes, programmation mathématique en variables binaires)

-       Méthodes d’optimisation combinatoire exactes ou approchées : heuristiques et métaheuristiques (méthode de descente, recuit simulé), programmation linéaire (algorithme du simplexe), relaxation lagrangienne, méthodes arborescentes par séparation et évaluation (branch and bound), programmation dynamique

-       Travaux pratiques (trois fois une heure trente) : méthode par séparation et évaluation appliquée au problème du voyageur de commerce (deux fois une heure trente, en C), métaheuristiques (méthode de descente, recuit simulé) appliquées au problème du voyageur de commerce (une heure trente, en Java), le principe étant dans les deux cas d’enrichir un programme fourni à l’élève de nouvelles fonctionnalités.

 

Prerequisites

-       Connaissances élémentaires en théorie des graphes

-       Connaissances élémentaires en algorithmique et en optimisation

-       Connaissances élémentaires en programmation en C et en Java

-       Motivation pour la modélisation mathématique et l’optimisation

-       Bonne connaissance du français.

 Nota : pour les élèves de Télécom ParisTech, ce cours n'est pas ouvert aux élèves qui suivront MITRO 205 ou ont déjà suivi INF 226 ou INFMDI340.

Course exam Examen écrit.
Back