Chef de l’équipe: AÏDER Méziane – Professeur, USTHB
A. OBJECTIFS D’ENSEMBLE
La “Combinatoire” désigne la discipline mathématique qui s’intéresse à l’étude des structures discrètes ou finies. Outre l’aspect énumératif, elle comprend notamment des branches telles que la théorie des graphes, la combinatoire énumérative, les problèmes de dénombrement, la combinatoire polyédrale, l’optimisation combinatoire et bien d’autres. Toutefois, il y a lieu de noter que les frontières entre les différentes branches ne sont pas du tout hermétiques, celles-ci exprimant d’avantage des schémas généraux d’orientations méthodologiques que des caractéristiques intrinsèques exhaustives et exclusives et dans une problématique donnée, il est souvent fait usage d’outils relevant de plus de ces branches. Ainsi, l’optimisation combinatoire utilise souvent un graphe comme modèle de base et fait appel à des techniques de résolution aussi bien basées sur des méthodes exactes que sur des heuristiques et métaheuristiques. En outre, l’optimisation classique a montré ses limites pratiques dans des situations fréquentes où plus d’un critère sont à optimiser. Une bonne solution pour un critère s’avère souvent plutôt mauvaise pour un autre (lorsque, par exemple, les objectifs sont contradictoires). Et c’est pour, justement, traiter ces situations que des méthodes multiobjectif ont été développées.
B. FONDEMENTS SCIENTIFIQUES
Deux thèmes de recherche sont développés aussi bien dans le cadre de la recherche formation (sujets de thèses de doctorat que nous encadrons) que dans le cadre de la recherche fondamentale et appliquée. Pour le premier, il s’agit de construire des classes de graphes les plus larges possibles satisfaisant certaines propriétés inhérentes à leur utilisation dans des situations concrètes de conception de réseaux. Un intérêt particulier est porté au problème de Moore (construction de graphes ayant le plus possible de sommets, pour un degré et un diamètre donnés) et aux problèmes de plongements de graphes. En ce qui concerne le second, il s’agit d’élaborer des algorithmes (exacts et approchés) pour la résolution de certains problèmes d’optimisation combinatoire mono‐objectif et multi‐objectif. Nous nous focalisons particulièrement sur les problèmes de placement, de sac à dos et des enchères combinatoires et utilisons particulièrement les approches polyédrales, les techniques branch and bound et les métaheuristiques.
C. MOTS‐CLÉS :
Problèmes métriques dans les graphes, Approche polyédrale, Métaheuristiques, Méthodes hybrides, Méthodes exactes, Optimisation combinatoire, Optimisation multiobjectif.