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
|
Ressources
en ligne |
> https://icampus.uclouvain.be/claroline/course/index.php?cid=LINMA2450
|
| Préalables |
Bases de programmation linéaires (dont dualité et algorithme du simplexe) telles qu'enseignées dans LINMA2471 (Modèles et méthodes d'optimisation).
|
| 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 |
Eu égard au référentiel AA, ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
Plus précisément, au terme du cours, l'étudiant sera capable de :
-
formuler différents problèmes combinatoires sous forme de programmes en nombre entiers
-
explorer différentes formulations pour un même problème, afin d'en faciliter la résolution
-
borner (inférieurement et supérieurement) la solution d'un programme en nombre entier
-
reconnaître des programmes en nombres entiers qui sont faciles à résoudre (en temps polynomial)
-
reconnaître des programmes en nombres entiers qui sont difficiles à résoudre (NP-complet)
-
appliquer des techniques heuristiques pour résoudre ces derniers de façon approchée
Acquis d'apprentissage transversaux :
-
usage de Matlab ou autres logiciels pour la résolution de problèmes de taille moyenne
|
Modes d'évaluation
des acquis des étudiants |
Examen écrit à livre fermé.
|
| Méthodes d'enseignement |
Une séance d'exercises a lieu toutes les deux semaines. Un ou plusieurs exercices à la maison avec utilisation d'un logiciel (Matlab ou autre) sera également proposé.
|
| Contenu |
-
Formulation de problèmes d'optimisation combinatoire et de programmation en nombre entiers
-
Techniques pour trouver des bornes sur la valeur optimale et en déduire l'optimalité le cas échéant
-
Comment reconnaître et résoudre certains problèmes faciles sur les flots, les arbres, les couplages et les assignations
-
Introduction à la distinction entre problèmes faciles et difficiles : la NP-complétude
-
Enumération intelligente: le branch-and-bound
-
La relaxation lagrangienne
-
Introduction aux plans de coupe
-
Méthodes heuristiques pour trouver des solutions approchées rapidement
|
| Bibliographie |
Integer Programming, L.A. Wolsey, Wiley, New York 1998.
|
Cycle et année
d'étude |
> Master [120] en sciences informatiques
> Master [120] : ingénieur civil en informatique
> Master [120] : ingénieur civil en mathématiques appliquées
|
Faculté ou entité
en charge |
> MAP
|
<<< Page précédente
|
