Descriptif
But: modéliser et traiter des problèmes d'optimisation discrète de grandes dimensions.Programme: limites des méthodes classiques; traitement des grands graphes; décomposition des problèmes et accélération des méthodes usuelles; la RO pour le machine learning (clustering, méthodes de PLNE pour l'apprentissage); parallélisme...
28 heures en présentiel
Diplôme(s) concerné(s)
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
MAP-RO
OROC-RO-PM
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil de 10)- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 1.5 ECTS
Le coefficient de l'UE est : 1
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Programme détaillé
1. Bloc de module:Séance 1 Analyse de la structure de grands réseaux
Comprendre la structure des réseaux est crucial dans de nombreux contextes, allant de la conception de protocoles à l'optimisation et à la prévision de l'évolution de ceux-ci. Dans ce contexte, la théorie des graphes fournit un ensemble de concepts importants permettant de caractériser la structure des réseaux en pratique. Ce premier cours a pour but de rappeler les bases de la théorie des graphes et ses liens avec l'analyse en réseau, ainsi que de montrer les solutions habituellement utilisées lorsque les algorithmes classiques ne passent pas à l'échelle.
2. CM:
Séance 2 Analyse et modélisation des réseaux dynamiques
Les éléments vus dans le cours précédent fournissent une première compréhension de la structure des réseaux mais reposent sur une vision statique de ceux-ci. Or dans de nombreux cas, la structure du réseau évolue au cours du temps. Ce second cours poursuit la réflexion entamée dans le cours précédent en montrant comment adapter les définitions classiques de la théorie des graphes au cas dynamique. Par ailleurs, ce cours abordera la question de la modélisation des graphes, en particulier de leur évolution, à travers un cas pratique.
3. TD en salle info:
TP portant sur le cours
4. Bloc de module:
Séance 3
- Branch and cut algorithms for Steiner Trees
- Benders decomposition for Facility Location
- Generalized Benders decomposition
5. Bloc de module:
Séance 4
- Introduction au phénomène de concentration de la mesure
- Lemme de Johnson-Lindenstrauss: projections aléatoires et réduction de dimension. Application aux problèmes de clustering
- Projections aléatoires et résolution de programmes linéaires de grandes tailles
6. PC:
Exercices d'application et d'approfondissement
7. PC:
Modeling session (exercises ):
- Models for connected facility location, ring-star problems, etc.
- With and without Benders decomposition
8. Contrôle: Examen écrit