| INMA2450 | Optimisation : programmation combinatoire |
|
[30h+15h]1q
|
|
Enseignant(s) :
Laurence Wolsey
|
 Objectifs
Décrire les principales approches pour résoudre des problèmes avec un nombre fini, mais énorme, de solutions possibles.Concentration sur la formulation et la résolution (si nécessaire approximative) de problèmes linéaires en nombres entiers.
Cahier des charges
Etude des différentes approches théoriques et algorithmiques pour la résolution de problèmes d'optimisation combinatoire. Les aspects théoriques concernent entre autre l'étude des polyèdres, des matrices, des graphes et une appréciation de la complexité (Polynomial NP Complex, etc...). Ensuite vient une appréciation de la « bonne » représentation ou modélisation des problèmes. L'aspect algorithmique traite les algorithmes d'énumération implicite, les méthodes de coupe, et de décomposition (relaxation Langrangienne), aussi bien que les algorithmes approximatifs. L'utilisation de logiciels appropriés pour résoudre des problèmes pratiques fait partie du cours.
Résumé
- Formulation de problèmes de décision sous forme de problèmes en nombres entiers : en particulier, problèmes de tournées (distribution), de localisation, de flot, de recouvrement, ainsi que d'autres problèmes associés à des graphes.
- Introduction à la théorie de la complexité et l'étude d'algorithmes efficaces pour les problèmes d'affectation et du plus court chemin.
- Etude d'algorithmes performants du type « Séparation et Evaluation » (« Brach and Bound »), « coupes fortes », et « relaxation Lagrangienne », destinés à résoudre des problèmes difficiles, en mettant l'accent sur la bonne formulation des problèmes posés, et y compris leur résolution pratique.
- Etude d'algorithmes d'approximation destinés à obtenir de bonnes solutions, non nécessairement optimales, en un temps limité.
- Dualité et analyse postoptimale dans la programmation linéaire en nombres entiers.
Le cours INMA2450 est mentionné dans les programmes suivants :
|
IAG3DS
|
Diplôme d'études spécialisées en administration et en gestion (Master in Business Administration)
|
| |
|
INFO2
|
Ingénieur civil informaticien
|
| |
|
MATH2
|
Licence en sciences mathématiques
|
| |
Valeurs ECTS de l'activité
|
ECGE3DS/MQ
|
Diplôme d'études spécialisées en administration et en gestion (Master in Business Administration) (méthodes quantitatives de gestion)
|
| |
|
IAG23M
|
Troisième année de Maîtrise en sciences de gestion (orientation "méthodes quantitatives de gestion")
|
| |
|
INGE23/G
|
Troisième Ingénieur de gestion (Générale)
|
| |
|
INGE23/I
|
Troisième Ingénieur de gestion (Internationale)
|
| |
|
INGE23/PM
|
Troisième Ingénieur de gestion (Création d'entreprise)
|
| |
|
MAP22
|
Deuxième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées
|
(4 ECTS)
| |
|
MATH22/G
|
Deuxième licence en sciences mathématiques
|
(4 ECTS)
| |
|
MATH22/I
|
Deuxième licence en sciences mathématiques (Informatique)
|
(4 ECTS)
| |
|
Valeur ECTS par défaut
|
(4 ECTS)
| |
|
