| 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
- 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 :
IAG2M Maîtrise en sciences de gestion (orientation "méthodes quantitatives de gestion")
IAG3DS Diplôme d'études spécialisées en administration et en gestion (Master in Business Administration)
INGE2 Ingénieur de gestion
MATH2 Licence en sciences mathématiques
|
