Les travaux de l’équipe « Optimisation Combinatoire » (OC) s’inscrivent dans le domaine de l’optimisation combinatoire, à la frontière de l’informatique et des mathématiques. Ils se déclinent en résultats portant sur des avancées théoriques et méthodologiques en optimisation d’une part, et d’autre part pour la résolution efficace de problèmes relevant de grands domaines d’application de la Recherche Opérationnelle (RO).
Les travaux de l’équipe OC relèvent de divers domaines d’application de la RO notamment la conception de réseaux, le développement durable et la biodiversité, l’ordonnancement et la planification ainsi que les problèmes génériques de graphes.
Pour les aspects théoriques et méthodologiques, les recherches de l’équipe portent principalement sur les 4 thèmes détaillés ci-dessous.
Conception de méthodes pour l’optimisation mathématique
Cette thématique couvre les travaux relevant de l’optimisation linéaire et non-linéaire en variables entières et continues. Nos travaux de recherche dans ce thème visent à proposer des méthodes efficaces de résolution exacte de problèmes en général difficiles. Pour ce faire, nous proposons des méthodes mathématiques de reformulation en des problèmes plus simples, de décomposition en plus petits problèmes, de projections et des approximations par des relaxations. Ces méthodes nous permettent de réduire le temps de calcul des algorithmes de résolution que nous mettons en œuvre tout en calculant des solutions optimales ou garanties proches d’une solution optimale. Ce type de résultats de recherche doit être validé par des expérimentations sur des jeux de données de benchmark développés par notre communauté scientifique.
Graphes et optimisation
Les graphes constituent un objet mathématique fondamental de la RO et l’équipe s’intéresse à des problèmes suffisamment généraux pour modéliser de nombreuses situations concrètes. Parmi ces problèmes, les « d−bloqueurs » consistent à déterminer le nombre minimal d’éléments à modifier (suppression, ajout, contraction) de sorte à dégrader (diminuer ou augmenter) la valeur du paramètre de d unités. Différents paramètres ont été étudiés : le couplage maximum, l’ensemble stable maximum et la couverture minimum, le nombre chromatique, le diamètre et le dominant minimum. D’autres travaux ont porté sur l’analyse structurelle et algorithmique du dominant de cardinalité minimum ainsi que sur la robustesse des graphes vis à vis de leur structure, notamment les couplages parfaits, les multicoupes (partielles ou non), la couverture par cycle et l’hamiltonicité. Dans tous les travaux liés à cette thématique, les recherches de l’équipe portent sur la conception d’algorithmes polynomiaux, exacts ou approchés, ou bien d’algorithmes FPT.
Robustesse et optimisation dans l’incertain
Une partie des activités de l’équipe porte sur la prise en compte d’incertitudes pour la résolution de problèmes d’optimisation sous l’angle de l’optimisation robuste qui consiste à déterminer des solutions « satisfaisantes » lorsque les paramètres incertains prennent les valeurs les plus défavorables ou encore sous l’angle de la programmation stochastique multi-étapes lorsque les lois de distribution des paramètres incertains sont connues.
Recherche opérationnelle et intelligence artificielle
Nous nous intéressons dans le cadre de différents travaux, à l’utilisation de techniques d’intelligence artificielle pour renforcer la résolution de problèmes d’optimisation discrète mais également à l’apport des techniques d’optimisation mathématique pour améliorer la qualité de prédiction et d’interprétabilité des arbres de classification.