Un problème d’optimisation combinatoire consiste à trouver la meilleure solution dans un ensemble discret de solutions appelé ensemble des solutions réalisables. En général, cet ensemble est fini mais de cardinalité très grande et il est décrit de manière implicite, c’est-à-dire par une liste de contraintes que doivent satisfaire les solutions réalisables. Pour définir la notion de meilleure solution, une fonction, dite fonction objectif, est introduite. Pour chaque solution, elle renvoie un réel, et la meilleure solution ou solution optimale est celle qui minimise ou maximise la fonction objectif. L’optimisation combinatoire s’applique ainsi à l’optimisation de l’architecture et du fonctionnement des systèmes de production, à l’optimisation des choix techniques ou technico-économiques concernant les produits (coûts, performances, fiabilité) et de façon générale, à l’optimisation des décisions prises dans l’Entreprise.
Les recherches de l’équipe OC se répartissent sur deux axes : Programmation mathématique et applications et Graphes et optimisation.
Axe « Programmation mathématique et applications »
Cet axe concerne essentiellement l’optimisation discrète (linéaire et non linéaire). Cette modélisation, extrêmement générale, permet de formuler de très nombreux problèmes d’optimisation combinatoire. Ces problèmes sont généralement difficiles et, dans beaucoup de cas, les problèmes de grande taille ne peuvent actuellement être résolus. Les travaux de l’équipe visent à une meilleure compréhension de ces problèmes dans le but d’améliorer leur résolution. Nous nous sommes également beaucoup intéressés à la résolution de problèmes d’optimisation industriels dans différents domaines : télécommunications, transports, énergies, environnement. Nous développons également des travaux concernant la recherche de solutions optimales robustes. Il est en effet souvent plus pertinent dans les applications industrielles de considérer une solution « robuste » qui se comportera bien dans toutes les situations susceptibles de se produire plutôt qu’une solution « optimale » pour une situation précise. L’équipe OC a déjà initié des travaux sur ce thème et la robustesse est source de très nombreuses problématiques.
Axe « Graphes et optimisation »
Les graphes constituent un outil mathématique fondamental de la Recherche Opérationnelle. Ils permettent la modélisation de systèmes extrêmement variés. L’obtention de solutions aux problèmes posés consiste généralement en la détection de structures optimales. De par la taille des problèmes posés la seule « puissance » des ordinateurs n’est pas suffisante pour mener à bien les calculs permettant d’obtenir une solution. Pour essayer de mener à bien cette résolution il est nécessaire de dégager des propriétés structurelles des solutions optimales pour développer, lorsque cela est possible, des algorithmes capables d’effectuer les calculs aboutissant à la résolution exacte ou approchée du problème considéré. L’axe Graphes et Optimisation a pour objectif de suivre cette démarche pour certains problèmes de graphes suffisamment généraux pour modéliser de nombreuses situations concrètes. Des travaux ont également été menés sur l’approximation polynomiale, les algorithmes paramétrés, et l’algorithmique online.