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 déterministe au stochastique, des graphes à la complexité algorithmique.
 La nature des problèmes d’optimisation étudiés est surtout combinatoire :

• 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.

Les problèmes d’optimisation combinatoire 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 exacts 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 de développer des algorithmes polynomiaux dont la valeur de la solution trouvée est comparable analytiquement à la valeur de la solution optimale. La mesure prise est le rapport d’approximation en pire cas, entre la valeur trouvée et la valeur de l’optimal. Des mesures de rapports d’approximation en moyenne sont aussi considérées lorsque cela peut être défini.

• Algorithmique des jeux : Il s’agit d’allier les mathématiques, l’économie et l’informatique pour gérer des situations de conflits d’intérêt individuel avec l’intérêt commun. L’application des algorithmes est récente : il s’agit de trouver les bonnes stratégies qui assurent une stabilité lors des échanges entre individus et des partages de ressources communes entre eux. L’algorithmique des jeux met l’accent sur la complexité du calcul de ces équilibres et s’appuie sur des bornes et approximations à performance garantie pour répondre à des modèles dont les solutions exactes sont irréalistes ou inconnues.

• Optimisation stochastique et robuste : Dans de nombreuses applications les données ne sont pas connues avec exactitude. L’incertitude associée est souvent représentée par plusieurs scénarios. Ces différents scénarios sont en général modélisés par l’ajout de nouvelles variables et contraintes.

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.