Optimisation et Recherche Opérationnelle

Les travaux de l'axe Optimisation et Recherche Opérationnelle sont centrés sur l’optimisation numérique (convexe et non convexe, différentiable et non différentiable), l’optimisation combinatoire (linéaire ou non linéaire, mono ou multi objectif) et la recherche opérationnelle (systèmes complexes, théorie des graphes, réseaux,...) ainsi que leurs applications industrielles, socio-économiques et logistiques.

Ces travaux touchent plusieurs axes de recherche tels que la programmation linéaire ou quadratique en nombres entiers, les approches de décomposition, les approches polyédrales, la génération de coupes et/ou de colonnes, les méthodes méta-heuristiques (dont les algorithmes évolutionnaires), les heuristiques hybrides.
Ils trouvent des applications dans différents domaines tels que l’ordonnancement (problèmes organisationnels, gestion d'emploi du temps,...), la recherche opérationnelle appliquée aux problèmes logistiques et industriels (gestion de stock, optimisation des flux, tournées de véhicules,...) et l'optimisation économique et financière (gestion de portefeuilles,
immunisation aux risques,...).

Ce thème s’inscrit ainsi pleinement dans la thématique fédératrice du laboratoire, les Systèmes Complexes. Les chercheurs impliqués dans ce thème articulent leurs recherches autour des méthodes suivantes.

  • Les Algorithmes Exacts: La plupart des programmes linéaires en nombres entiers (PLNE) sont très difficiles à résoudre et sont classés dans la famille des problèmes NP-difficiles. On s'intéresse à la formulation de ces problèmes et aux techniques de décomposition et de reformulation, comme celle de Dantzig-Wolfe. Une partie de notre recherche est axée sur la méthode de génération de colonnes et de coupes et l'algorithme de Branch-and-Price-and-Cut pour résoudre des PLNE de grande dimension. Ces méthodes génériques consistent à décomposer le problème et à résoudre, d’une manière itérative, une série de problèmes de plus petites tailles, en vue d’obtenir une solution optimale du problème initial. Ces méthodes peuvent aussi servir de base pour trouver une solution approchée au problème.
  • Les Algorithmes Approchés: Les méthodes méta-heuristiques sont des règles empiriques simples ou des algorithmes stochastiques itératifs qui, à la différence des algorithmes exacts, ne se basent pas sur des analyses scientifiques trop complexes, mais plutôt sur l’expérience, l’analogie et des résultats déjà obtenus pour optimiser les recherches suivantes. En général, la solution obtenue n’est pas optimale pour le problème traité et représente une solution approchée. Souvent, les méta-heuristiques disposent d’une simplicité et donc d'une rapidité dans leur exécution plus élevée que les algorithmes exacts. C’est le cas, par exemple, lorsque la résolution exacte du problème nécessite un temps d’exécution trop élevé ou une grande mémoire de stockage. Les méthodes méta-heuristiques, souvent inspirées par des systèmes naturels, peuvent être classées en deux catégories:

    • Les méta-heuristiques à parcours font évoluer une seule solution sur l’espace de recherche local à chaque itération puis la compare aux meilleures solutions déjà obtenues. Ces méta-heuristiques génèrent une suite des itérés qui améliore la valeur de la meilleure solution, en espérant atteindre l'optimum. Les méthodes les plus connues dans cette classe de méta-heuristiques sont le recuit simulé et la recherche tabou.

    • Les méta-heuristiques à population utilisent un échantillonnage de solutions comme base d’apprentissage. A chaque itération, ces algorithmes disposent d’un ensemble de solutions réalisables qui sont combinés de façon à améliorer la valeur de la meilleure solution dans l'espoir d'atteindre la solution optimale. Parmi les algorithmes de cette classe, on peut citer les algorithmes génétiques et les algorithmes de colonies de fourmis.
  • Les Algorithmes Hybrides:Pour éviter les minimums locaux et accélérer la convergence des méthodes exactes ou approchées, l'équipe développe des algorithmes hybrides. Elles sont constitués soit d’une combinaison de plusieurs méthodes méta-heuristiques, soit d'une combinaison de méta-heuristique avec des méthodes exactes.

  • Les Méthodes de Décomposition Convexe (Décomposition DC): Un problème d’optimisation de la forme (P) : min{F(x): x S} est dit non convexe si la fonction F et/ou l’ensemble S est non convexe. Dans ce cas, la résolution du problème est très difficile. En général, on le résout en résolvant une série des problèmes convexes. Dans certains cas, il est possible de transformer ce problème en un problème équivalent sous forme de minimisation de différence de deux fonctions convexes, appelée décomposition par différence convexe (décomposition DC): (DC) : min { f(x) = g(x) – h(x) : x R n } où g et h sont deux fonctions convexes.
    En déterminant une décomposition DC convenable, on arrive à résoudre efficacement (P). Des algorithmes spécifiques sont alors utilisés pour résoudre ce type de problèmes.

  • Les Méthodes de points Intérieurs: Les méthodes de points intérieurs ont été inspirées par l’algorithme de Karmarkar, développé en 1984, pour résoudre un programme linéaire. L’idée de base est d’utiliser des fonctions barrières pour décrire l’ensemble des solutions qui est convexe, de par la définition du problème. Les méthodes de points intérieurs se répartissent en plusieurs familles :

    • Les méthodes « Affine Scaling » (optimisation sur des ellipsoïdes),

    • Les méthodes de réduction du potentiel (notion de barrière, chemin central, relaxation).

    Ces méthodes ont connues une énorme évolution depuis 1985 et ont été généralisées à la résolution de problèmes non convexes. La notion des fonctions barrières, appelées fonctions noyaux, a abouti à des algorithmes de comportements théorique et numérique intéressants. Notre objectif consiste à améliorer la complexité algorithmique de ces méthodes.