Realopt
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 slides

Revoir le live :



François Clautiaux
Professeur à l'Université de Bordeaux Institut de Mathématiques de Bordeaux, équipe Inria RealOpt


S'inscrire !
Nos sponsors

Les stands partenaires

{\rtf1}