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, Dossier
• Durée : 1h30
• Précisions : Le contrôle continu représente les 50 % restants et comprend un devoir écrit ou sur machine comptant pour 25 % et un projet comptant pour 25 %.

Contrôle Terminal
• Type : Écrit
• Durée : 1h30
• Précisions : Durée susceptible d’être ajustée en fonction des contraintes pédagogiques, matérielles ou logistiques, dans le respect des M3C applicables. L’examen final représente 50 % de la note finale

Régime Dérogatoire
• Type : Écrit
• Durée : 1h30
• Précisions : Durée de 1h30 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 : 1h30
• Précisions : Durée 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 :
Dans le cadre de cet EC, l’usage de l’IA pour aider à la réalisation des travaux soumis à évaluation

• est autorisé pour les tâches suivantes : 
  *** documentation (identification de ressources pertinentes, synthèse de travaux existants, état de l’art)
  *** recherche d’idées (explicitation du sujet, “brainstorming”)
  *** édition (correction de fautes d’orthographe et de syntaxe, mise en forme des références, traduction de citations et d’extraits).
• Il est interdit pour les tâches suivantes :
  *** construction (problématisation, suggestion de plan)
  *** rédaction (amélioration du style, réécriture de passages, rédaction de résumés)

Les résultats fournis par l’IA doivent constituer un matériau pour votre réflexion, et toujours faire l’objet d’une réappropriation et d’une reprise critique.
Tous les usages doivent être documentés dans une section dédiée à la fin de votre travail, à l’exception des usages de recherche web augmentée, de correction orthographique et syntaxique. Cette section doit permettre à votre lecteur d’évaluer la manière dont vous avez travaillé avec l’IA et mobilisé cette ressource au service d’un travail personnel.

L’intégration directe de contenus engendrés par l’IA doit être faite sous le régime de la citation

Algorithmique et programmation S5 et Recherche opérationnelle S6

• 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.