• Niveau d'étude

    BAC +4

  • ECTS

    3 crédits

  • Composante

    Sciences économiques, gestion, mathématiques et informatique

  • Volume horaire

    36h

  • Période de l'année

    Enseignement huitième semestre

Objectifs

Il s'agit de développer chez l'étudiant à la fois les capacités d'abstraction, de modélisation, d'algorithmique et d’expérimentation. Le champ d'application choisi : les problèmes d'optimisation combinatoire.

Approche pédagogique et plan de cours.

Ces points sont traités dans un ordre variable, selon l’avancement des étudiants. Les volumes horaires sont indicatifs et adaptables : Chaque partie est composée de cours, de TD sur papier et de TD machine (on va du modèle à l'implémentation en java). Le problème du Sac à Dos est utilisé comme fil conducteur pour présenter les différentes approches. D’autres problèmes sont également abordés.

  • Modélisation mathématique de problèmes "industriels", avec utilisation d'un langage de modélisation et d'un solveur.
  • Techniques génériques de calcul de bornes (relaxation et construction rapide de solutions réalisables).
  • Méthodes arborescentes (énumération implicite) basées sur les calculs de bornes du chapitre précédent,
  • Mesure empirique et théorique de la qualité des bornes (algorithmes approchés),
  • Approche de recherche locale et métaheuristique (représentation d'un réseau réticulé de solutions),
  • Programmation dynamique (représentation d’une solution par un chemin dans un graphe d'état),
Lire plus

Évaluation

Session 1 : Évaluation continue (cf. règle par défaut de la section « Modalités spécifiques » des M3C spécifiques)

Session 2 : Règle par défaut décrite dans la section « Modalités de contrôle et examens / Modalités spécifiques »

Lire plus

Heures d'enseignement

  • Optimisation CombinatoireCM18h
  • Optimisation CombinatoireTD18h

Pré-requis obligatoires

  • Connaissances de niveau L3 en algorithmique de graphes et en programmation linéaire. Aisance avec les symboles mathématiques.
Lire plus

Compétences visées

  • Modéliser mathématiquement un problème d’optimisation combinatoire décrit en langage naturel
  • Identifier des similitudes entre problèmes issus d'horizons industriels différents
  • Identifier les causes de l’explosion combinatoire d’un algorithme
  • Manipuler au moins deux représentations d’un problème d’optimisation combinatoire et décrire les algorithmes de résolution qui en découlent
  • Mesurer empiriquement et parfois théoriquement la qualité des solutions fournies par un algorithme.
Lire plus

Bibliographie

Recherche opérationnelle - Tome 1 Méthode d'optimisation, Jacques Teghem Eyrolles

Lire plus