Note du 29 juin 2020
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.
5 crédits
30.0 h + 22.5 h
Q1
Enseignants
Delvenne Jean-Charles (coordinateur); Hendrickx Julien;
Langue
d'enseignement
d'enseignement
Anglais
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
d'apprentissage
A la fin de cette unité d’enseignement, l’étudiant est capable de : | |
| 1 |
Eu égard au référentiel AA, ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
|
La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».
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
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é.
Modes d'évaluation
des acquis des étudiants
des acquis des étudiants
Examen écrit à livre fermé.
Ressources
en ligne
en ligne
Bibliographie
Integer Programming, L.A. Wolsey, Wiley, New York 1998.
Faculté ou entité
en charge
en charge
MAP
Programmes / formations proposant cette unité d'enseignement (UE)
Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
d'apprentissage
Master [120] : ingénieur civil en science des données
Master [120] en sciences mathématiques
Master [120] : ingénieur civil en informatique
Master [120] : ingénieur civil en mathématiques appliquées
Master [120] en sciences informatiques
Master [120] en science des données, orientation technologies de l'information