Flot et Combinatoire

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.

Introduction à la RO

# 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