Objectifs (en termes de compétences)

Dans ce cours, nous examinons des méthodes efficaces pour résoudre des problèmes d'optimisation discrète qui sont posés en étudiant des graphes, la gestion de la production, la logistique, la conception de circuits, etc. Etant donné que la plupart des problèmes pratiques sont "difficiles", le but principal est de comprendre comment modéliser de tels problèmes et ensuite choisir un algorithme approprié - énumération implicite, méthode de coupes, décomposition, heuristique - afin d'obtenir une solution optimale ou avec une garantie d'être proche de l'optimum.

Objet de l'activité (principaux thèmes à aborder)

Dans ce cours nous examinons des méthodes différentes pour résoudre un problème d'optimisation avec des indivisibilités, ou des décisions oui/non concernant le choix d'une arête dans un graphe, l'achat d'une machine, l'utilisation d'un dépot, etc. De tels problèmes sont posés dans la construction d'un horaire de train ou d'avion, d'un tour dans un graphe, d'un plan de génération journalier d'électricité, etc. La théorie concerne les polyèdres, matrices, graphes et certains aspects de la complexité. Les approches algorithmiques étudiées sont l'énumeration implicite et les méthodes de coupes (branch-and-cut), relaxation lagrangienne, programmation dynamique et les algorithmes d'approximation.

Résumé : Contenu et Méthodes

Cours 1: Formulation de problèmes d'optimisation combinatoire et d'optimisation en nombres entiers.
Cours 2: Génération de bornes sur la valeur optimale et preuves d'optimalité.
PROBLEMES FACILES
Cours 3: Reconnaissance de problèmes faciles - flot dans un réseau, arbres
Cours 4: Problèmes de couplage et d'affectation
Cours 5: La distinction entre problèmes faciles et difficiles - éléments de complexité
PROBLEMES DIFFICILES
Cours 6: Enumération intelligente - l'algorithme d'énumération implicite (séparation et évaluation)
Cours 7: Relaxation lagrangienne- une approche par décomposition
Cours 8: Approche géométrique - algorithmes de coupes générales
Cours 9: L'utilisation de la structure - algorithmes de coupes specialisées - branch-and-cut
Cours10: Méthodes heuristiques pour trouver de bonnes solutions rapidement
AUTRES SUJETS
Cours 11: Problèmes résolus par programmation dynamique
Cours 12: Décomposition par génération de colonnes
Cours 13: Plus sur la modélisation et la résolution de problèmes

Autres informations (Pré-requis, Evaluation, Support, ...)

Une séance d'exercises a lieu toutes les deux semaines. Les étudiants doivent utiliser un système de modélisation et d'optimisation pour résoudre quelques instances pratiques. Ils doivent aussi programmer et tester un des algorithmes vu au cours.
REFERENCE: Integer Programming, L.A. Wolsey, Wiley, New York 1998.

Autres crédits de l'activité dans les programmes