Optimisation combinatoire

Ce cours approfondit les méthodes permettant de résoudre des problèmes d’optimisation portant sur des ensembles finis mais souvent très grands de solutions possibles. Il s’inscrit dans la continuité de la recherche opérationnelle, en mettant l’accent sur les problèmes où les décisions sont discrètes, comme choisir un sous-ensemble, ordonner des tâches, construire un chemin, affecter des ressources ou sélectionner une configuration optimale.

Les problèmes étudiés pourront inclure, selon les choix pédagogiques, le sac à dos, le voyageur de commerce, la coloration, le vertex cover, les problèmes d’affectation, de planification, de tournées ou de sélection sous contraintes ainsi que des problèmes multi-objectifs. Ces exemples serviront à introduire différentes familles de méthodes, notamment les formulations en programmation linéaire en nombres entiers, les méthodes exactes comme la programmation dynamique et les méthodes approchées comme les algorithmes gloutons, la recherche locale et les métaheuristiques.

Le cours mettra l’accent sur la modélisation, la complexité, la qualité des solutions obtenues et le compromis entre optimalité et temps de calcul suivant la taille des instances. Des outils informatiques, ainsi que des LLM et agents, pourront être mobilisés pour aider à formaliser un problème, produire du code, générer des instances de test, comparer des méthodes ou analyser expérimentalement les résultats.

À l’issue du cours, les étudiants devront être capables de :
• identifier un problème d’optimisation combinatoire ;
• modéliser un problème discret à partir d’un énoncé concret ;
• distinguer solution admissible, solution optimale, fonction objectif et contraintes ;
• reconnaître quelques problèmes classiques et leurs variantes ;
• comprendre les enjeux liés à la complexité et à l’explosion combinatoire ;
• formuler certains problèmes sous forme de programmes linéaires en nombres entiers ;
• appliquer des méthodes exactes ou approchées adaptées au contexte ;
• comparer des algorithmes selon leur qualité de solution, leur temps de calcul et leur robustesse ;
• mettre en œuvre une démarche expérimentale pour évaluer des méthodes d’optimisation ;
• utiliser des outils d’IA générative pour assister la modélisation, l’implémentation ou l’analyse, tout en validant rigoureusement les résultats.

Modalités : Mixte : CC + CT
SESSION 1 :
Contrôle Continu
• Type : Écrit, QCM, Oral
• Durée : 2h00
• Précisions : Une durée indicative de 2h00, susceptible d’être ajustée en fonction des contraintes pédagogiques, matérielles ou logistiques, dans le respect des M3C applicables.

Contrôle Terminal
• Type : Écrit
• Durée : 2h00
• Précisions : Une durée indicative de 2h00, susceptible d’être ajustée en fonction des contraintes pédagogiques, matérielles ou logistiques, dans le respect des M3C applicables.

Régime Dérogatoire
• Type : Écrit
• Durée : 2h00
• Précisions : Une durée indicative de 2h00, susceptible d’être ajustée en fonction des contraintes pédagogiques, matérielles ou logistiques, dans le respect des M3C applicables.

SESSION 2 :
• Type : Écrit
• Durée : 2h00
• Précisions : Une durée indicative de 2h00, susceptible d’être ajustée en fonction des contraintes pédagogiques, matérielles ou logistiques, dans le respect des M3C applicables.

Utilisation de l'intelligence artificielle :
L’utilisation de l’Intelligence Artificielle est interdite lors des évaluations.

Algorithmique et programmation et Recherche opérationnelle

• Modéliser des problèmes de décision et d’optimisation discrète.
• Construire une formulation mathématique à partir d’un problème concret.
• Manipuler des contraintes, des variables de décision et des fonctions objectif.
• Comprendre les limites des approches exhaustives face à l’explosion combinatoire.
• Choisir une méthode de résolution adaptée au problème et aux ressources disponibles.
• Implémenter et tester des algorithmes exacts ou approchés.
• Évaluer expérimentalement la performance d’une méthode d’optimisation.
• Interpréter les résultats obtenus et discuter leur qualité.
• Utiliser des outils numériques, des solveurs et des agents d’IA comme supports d’expérimentation et d’aide au développement.
• Développer une démarche rigoureuse de résolution, combinant modélisation, calcul, validation et analyse critique.