Recherche Opérationnelle Avancée

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

1. Leçon 1 — Optimisation Non Linéaire
2. Leçon 2 — Programmation Dynamique
3. Leçon 3 — Théorie des Jeux
4. 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).