Amphi 2 - SESSION 3.2 - 07/02/2018 17:00 > 17:30
Des horaires de train à la découpe de verre : ubiquité des modèles de flots en optimisation
1. Introduction
Ces dernières années ont vu une amélioration considérable de la puissance des solveurs génériques de programmation linéaire en nombres entiers. Ils sont aujourd'hui des outils très puissants pour résoudre des problèmes difficiles d'optimisation.
Un enjeu important dans l'utilisation de ces solveurs est de trouver la bonne manière de formuler les problèmes que l'on veut résoudre. L'efficacité des algorithmes est en effet très dépendante du choix de la formulation.
2. Méthodologie
Une manière efficace de modéliser un problème est de le représenter sous la forme d'un problème de flot dans un réseau. Les modèles obtenus ont de bonnes propriétés théoriques et permettent de mettre en place des algorithmes qui leur sont dédiés.
Nous illustrons ce type de modèles en montrant comment ils ont été utilisés pour résoudre des problèmes industriels dans le cadre de l'équipe RealOpt : planification de la production d'énergie, découpe de verre, emplois du temps, horaires de train, parmi d'autres.
3. Originalité / perspective
Les modèles de flot sont très faciles à mettre en place lorsque les paramètres du problème permettent de se limiter à un réseau de taille raisonnable. Un champ de recherche très important consiste à déterminer des stratégies pour obtenir des algorithmes efficaces lorsque ces paramètres sont moins favorables à l'usage direct de ces modèles.
Télécharger les slidesRevoir le live :
Professeur à l'Université de Bordeaux
Institut de Mathématiques de Bordeaux, équipe Inria RealOpt