Composante
ENSEIRB-MATMECA
Code interne
EI8IF230
Description
La sécurisation et le dimensionnement des réseaux (urbain, informatique, de télécommunication,...), l'optimisation du routage des flux (financiers, d'information, de personnels, de produits), les problèmes de logistique et de transport (routier, aérien et du rail) représentent de réels enjeux pour les industriels. Les problèmes d'optimisation sous-jacents se ramènent le plus souvent à des modèles combinatoires qui sont des briques essentielles pour appréhender les systèmes complexes.
Ce cours vise à compléter la formation aux approches algorithmiques spécifiques aux problématiques d'optimisation combinatoire dans les graphes. Le cours vise à expliquer comment utiliser les outils de la programmation mathématique (typiquement la programmation linéaire et en nombre entiers) pour guider les algorithmes combinatoires vers des solutions optimales ou quand cela s'avère trop complexe, de bonne solutions approchées. L'objectif est de maîtriser les modèles et techniques de base qui servent dans les stratégies de résolution d'une grande variété de problèmes complexes.
Heures d'enseignement
- CICours Intégré26h
- TITravaux Individuels25h
Pré-requis obligatoires
Introduction à la RO
Syllabus
# Optimisation de flot dans les réseaux : rappel des modèles et algorithmes de base.
# Polyèdres et combinatoires : Algorithmes primaux-duaux et Algorithmes d'Approximation basés sur la programmation linéaire
Modalités de contrôle des connaissances
Évaluation initiale / Session principale - Épreuves
Type d'évaluation | Nature de l'épreuve | Durée (en minutes) | Nombre d'épreuves | Coefficient de l'épreuve | Note éliminatoire de l'épreuve | Remarques |
---|---|---|---|---|---|---|
Contrôle Continu Intégral | Contrôle Continu | 1 |