Ce cours prolonge la Recherche Opérationnelle de S3 (programmation linéaire, graphes) vers des outils plus puissants, largement utilisés en génie logiciel, en réseaux et en science des données : l’optimisation non linéaire (au cœur de l’apprentissage automatique), la programmation dynamique (algorithmes de chaînes, de graphes, de cache), la théorie des jeux (systèmes multi-agents, enchères de ressources, concurrence entre fournisseurs) et les méta-heuristiques (problèmes combinatoires trop grands pour les méthodes exactes). Chaque notion est illustrée par un calcul à la main et par un programme Python exécuté, sur des cas concrets : réseau fibre d’une commune, tournée d’agences d’une microfinance, cache d’une application e-commerce, routeurs Niamey–Maradi.
Objectifs d’apprentissage
- Maîtriser les méthodes d’optimisation non linéaire appliquées aux systèmes informatiques.
- Appliquer la théorie des jeux aux problèmes de décision dans les systèmes multi-agents.
- Utiliser la programmation dynamique pour résoudre des problèmes complexes d’optimisation.
- Concevoir et analyser des algorithmes d’optimisation méta-heuristiques.
Prérequis
Recherche Opérationnelle (ROP3112, GELO S3) ; Mathématiques Discrètes & Logique (MDS2121). Sont supposés acquis : dérivées partielles, calcul matriciel élémentaire, graphes, programmation Python (listes, fonctions, boucles).
Plan du cours
- Leçon 1 — Optimisation Non Linéaire
- Leçon 2 — Programmation Dynamique
- Leçon 3 — Théorie des Jeux
- Leçon 4 — Méta-heuristiques
Travaux pratiques
- TP Python : implémentation d’un algorithme génétique pour l’optimisation d’un réseau (Leçon 4), avec comparaison à la solution exacte.
- TD intégrés : descente de gradient et Newton à la main, KKT, sac à dos et Floyd-Warshall, stratégies mixtes, enchères, recuit simulé et colonies de fourmis.
Modalités d’évaluation
Volume horaire : CM 20 h, TD 10 h, TP 0 h, TPE 30 h (CTT 60 h) — 3 crédits. Évaluation CC + ET : contrôle continu 30 % (TD, programmes rendus), examen terminal 70 % ; nature mixte.
Bibliographie
- F. S. Hillier & G. J. Lieberman, Introduction to Operations Research, McGraw-Hill.
- J. Nocedal & S. J. Wright, Numerical Optimization, Springer.
- T. H. Cormen et al., Introduction to Algorithms (chapitres programmation dynamique et plus courts chemins), MIT Press.
- S. Boyd & L. Vandenberghe, Convex Optimization, Cambridge University Press (disponible en ligne).
