<- Archives UCL - Programme d'études ->



Combinatorial optimization [ LINMA2450 ]


5.0 crédits ECTS  30.0 h + 22.5 h   1q 

Enseignant(s) Delvenne Jean-Charles ;
Langue
d'enseignement:
Anglais
Lieu de l'activité Louvain-la-Neuve
Thèmes abordés 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.
Acquis
d'apprentissage
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.
Contenu 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 infos 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.
Cycle et année
d'étude
> Master [120] : ingénieur civil en informatique
> Master [120] en sciences informatiques
> Master [120] : ingénieur civil en mathématiques appliquées
> Master [120] en statistiques, orientation générale
Faculté ou entité
en charge
> MAP


<<< Page précédente