Optimisation Combinatoire

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),

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 »

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

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

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