Présentation

Ce thème concerne la modélisation et la recherche d’algorithmes efficaces pour différents problèmes d’optimisation issus de la recherche opérationnelle et des mathématiques appliquées. Le contexte applicatif est très large, allant du continu au discret, du déterministe au stochastique, des graphes aux modèles variationnels.
La nature des problèmes d’optimisation étudiés est :

• Combinatoire : trouver le plus petit ou le plus grand élément parmi un ensemble fini d’éléments. Les variables prennent alors des valeurs entières.

• Continue : trouver le plus petit ou plus grand point d’un ensemble infini non-dénombrable. Les variables peuvent prendre des valeurs réelles.

Les problèmes d’optimisation sont étudiés à travers plusieurs approches selon leurs difficultés et leurs structures :

• Approches polyédrales : il s’agit de ramener le problème à la résolution d’un programme linéaire. Cette tâche est impossible quand le problème en question est NP-complet, mais la détermination d’un programme linéaire relaxé est facile et offre en général des bornes très utiles pour entamer la résolution par des algorithmes de branch-and-bound-and-cut. Ce sont les algorithmes exactes les plus performants pour résoudre les problèmes d’optimisation combinatoire difficiles. Cette approche est aussi utilisée pour décrire des instances où un problème NP-complet devient polynomial. Ceci est réalisé en décrivant complètement le polytope associé au problème par un programme linéaire avec des contraintes faciles à séparer (nous pouvons introduire en un temps polynomial les contraintes nécessaires à l’optimisation malgré leur nombre exponentiel dans la plupart des cas).
• Algorithmes d'approximation : il s'agit ici de proposer, pour des problèmes difficiles, des algorithmes produisant en temps polynomial des solutions dont on peut analytiquement garantir la qualité (sa taille, son poids, etc.) par rapport à la solution optimale.   

• Les extensions de la notion de convexité, la relation entre optimalité globale et optimalité locale. On s’attache ici à rapprocher les modèles non convexes des modèles combinatoires par différentes reformulations.

• Les schémas de décomposition primale et duale des systèmes complexes. 

Les problèmes étudiés sont issus de divers domaines : réseaux de transport, réseaux de télécommunication, réseaux électriques, bio-informatique, réseaux de capteurs, localisation des infrastructures, nucléaire, automobile.