IMB > Recherche > Equipes

Recherche opérationnelle

<rubrique29|equipe2>

Membres permanents

Responsable : François Vanderbeck

Positionnement Scientifique

L’aide à la décision via des modèles combinatoires d’optimisation sous contraintes reste un vrai défi. La complexité de résolution croît de manière exponentielle avec la taille des jeux de données traités. Les progrès consistent à faire reculer le seuil de l’explosition combinatoire en développant des techniques d’énumération dites intelligentes par lesquelles des approximations de qualité permettent d’éliminer bon nombre de solutions sous-optimales. Notre équipe se place résolument dans le développement de méthodologies d’optimisation mathématique permettant le passage à l’échelle, d’intégration des niveaux de décision, d’optimisation robustes aux aléas, et de ré-optimisation dynamique.

Les approximations de qualité nécessaire pour tronquer l’énumération dans la résolution des problèmes combinatoires reposent pour beaucoup sur des modélisations mathématiques donnant des formulations dites fortes (où l’approximation continue a une valeur proche du problème en variables discrètes). Nos approches pour développer ce type de qualité de formulation consistent à user de principes de décomposition exploitant les caractérisations combinatoires de sous-sytèmes types (par exemple issus de la théorie des graphe) et à modéliser le problème dans un espace étendu de variables. Il devient alors clé de gérer le nombre exponentiel de variables et contraintes de manière dynamique, en les générant en cours d’optimisation quand ces entités deviennent actives dans la solution. La gestion dynamique du modèle grande échelle passe aussi par des techniques d’intensification et diversification de la recherche de solution qui se traduisent par aggregation et dessagregation de variables et contraintes, par des techniques de prétraitement (fixation de variables, élimination de contraintes) basées sur l’intelligence artificielle, et par des techniques de renforcement par l’ajout d’inégalités valides basées sur l’étude polyédrale. Les approches de décomposition constituent également un fer de lance dans le traitement des aléas. Les modèles d’optimisation robuste s’apparentent à un modèle de théorie des jeux avec des décisions prises au premier niveau avant que l’aléa ne soit révélé en minimisant l’effet de la pire réponse possible de l’adversaire modélisée comme un problème de second niveau. Si un recours est possible, il s’ajoute en troisième niveau. Nos méthodologies sont validées et transférées par le biais de notre plateforme logicielle, BaPCod. Nos progrès se mesurent à l’échelle des applications industrielles que nous traitons et des résultats de référence que nous obtenons sur des modèles combinatoires phare.

Equipe INRIA RealOpt

Notre équipe est structurée autour d’un projet de recherche INRIA en collaboration avec des membres du laboratoire d’informatique (le LaBRI).

Evolution

L’équipe RO va être remodelée au 1er janvier 2016 en intégrant d’autres chercheurs de l’IMB pour former l’équipe « OptimAl : Optimisation Mathématique, Modèles Aléatoires, et Statistique » dont les thèmes sont :

Les recherches d’OptimAl se concentrent sur le développement d’outils mathématiques pour la modélisation de systèmes aléatoires (inférence, analyse de données), ainsi que la résolution et l’analyse de problèmes d’optimisation (optimisation combinatoire et contrôle stochastique) ou d’évaluation (statistique) de performances. Les modèles mathématiques considérés traitent de systèmes complexes présentant le plus souvent un comportement dynamique et/ou aléatoire. Ces systèmes sont susceptibles d’être optimisés suivant différents critères : synthèse de décisions réalisables, prédiction, recherche de stratégie… Les contributions consistent à proposer des outils théoriques, des méthodologies de résolution garantissant validité et convergence, ainsi que des implémentations algorithmiques efficaces. Le spectre des compétences va de l’étude théorique au développement d’outils numériques qui permettent le passage à l’échelle sur des problèmes pratiques.