SAMOVAR UMR 5157

  • Accueil
  • Accueil
  • Accueil
  • Accueil

CNRS

Rechercher




Accueil > Équipes > METHODES > Bilan scientifique 2008-2013 > Axes de recherche

Optimisation

  • Enseignants-chercheurs : Walid BEN-AMEUR, Jérémie JAKUBOWICZ, José NETO
    • Thèses soutenues : 2
    • Thèses en cours : 5

Optimisation combinatoire

Une partie des travaux traite des problèmes de partitionnement de graphes. Nous avons par exemple traité du problème de la coupe maximum pour lequel nous avons proposé une approche géométrique reposant sur des formulations particulières du problème et mettant également en oeuvre de la programmation semidéfinie [386]. Un algorithme basé sur une adaptation de l’algorithme du sous-gradient a également été étudié [356]. Afin d’améliorer les méthodes de résolution de type plans coupants, nous avons proposé une approche polyédrique visant à étendre les connaissances relatives à la structure géométrique du polytope des coupes [362].

Nos travaux ont également porté sur le problème du k-séparateur où il s’agit de supprimer d’un graphe donné un sous-ensemble de sommets de poids total minimum tout en garantissant que chaque composante connexe du différentes formulations, étude polyédrique, algorithmes d’approximation, résultats d’inapproximabilité, implémentation informatique) [462]. Ce travail a été soutenu par un financement de l’IMT (Institut Mines-Télécoms).

Le problème de la coupe séparatrice dans un graphe qui a été présenté comme problème ouvert dans une journée du GDR RO, a été étudié dans [354]. Un algorithme polynomial ainsi qu’une formulation compacte du problème ont ainsi été proposés.

L’équipe a aussi investigué le problème de graphes à composantes connexes unicycliques. Nous avons notamment montré que la variante de Steiner où on impose que certains sommets appartiennent aux cycles, se résout en temps polynomial. Ce travail a été réalisé dans le cadre d’un projet bilatéral avec Orange Labs et a donné lieu à deux articles de revue [328, 373] dont un dans SIAM Journal on Discrete Mathematics.
Les travaux sus-mentionnés relatifs au problème de la coupe maximum dans un graphe nous ont conduit à des études d’extentions possibles des résultats obtenus à des formes plus générales de problèmes. Celles-ci ont permis d’aboutir à la découverte de nouvelles bornes de la valeur optimale de problèmes d’optimisation quadratique en variables bivalentes [365]. Ces travaux ont été publiés dans la revue European Journal of Operational Research.

Une autre retombée significative des études menées en lien avec le problème de coupe maximum et faisant suite aux extensions mentionnées plus haut, a consisté en l’identification d’un ensemble de problèmes quadratiques en variables bivalentes solubles en temps polynomial ainsi que le développement et l’évaluation d’une approche récursive originale efficace pour traiter ce type d’instances [364].

Dans la continuité d’anciens travaux de l’équipe, notre attention s’est portée sur la mise en oeuvre des algorithmes à plans coupants dans le contexte des programmes mixtes/entiers qui sont notoirement difficiles. Un algorithme de plans coupants fini a ainsi été proposé [350].

L’équipe poursuit l’investigation des problématiques d’écoulement de multiflots dans un graphe. De nouvelles méthodes de décomposition ont pu être développées pour résoudre des problèmes de grandes tailles. Un algorithme combinatoire fortement polynomial a également été proposé pour le cas mono-source du problème de maximum concurrent flot [333]. Ce travail se fait dans le cadre d’une CIFRE avec Orange Labs.

Toujours dans ce contexte d’écoulement de flots, dans le cas où certains arcs d’un graphe sont fiables et d’autres sont susceptibles de tomber en panne, nous nous sommes intéressés au problème de calcul d’une paire de chemins de coût minimum ne partageant que des liens fiables. Un algorithme polynomial a été proposé pour ce problème [369, 355].

Optimisation stochastique distribuée

Dans cet axe, nous nous sommes intéressés à différents problèmes distribués. Dans [323], nous avons étudié le comportement d’un algorithme qui cherche à minimiser une fonction f =Pv2V fv qui est la somme d’un certain nombre de fonctions fv connues uniquement par un agent v dans un réseau V . Ainsi le réseau dans son ensemble
cherche à minimiser une fonction qu’aucun de ses membres ne connaît intégralement. En collaborant, les agents peuvent toutefois arriver à s’approcher des minimas cherchés lorsqu’ils existent. Notre apport dans [323] a consisté à considérer le cas de fonctions non nécessairement convexes en présence de contraintes.

Les outils de consensus sont fondamentaux pour ce problème d’optimisation distribué dans le sens où les agents du réseau doivent s’entendre sur la valeur du minimum cherché. Ceci nous a poussé à explorer les algorithmes de consensus. Dans [338], nous nous sommes intéssés au max-consensus. Dans [435], nous nous sommes intéressés au problème du consensus robuste, où des agents têtus cessent de se mettre à jour et continuent à inonder le réseau avec la même information. Dans [571] nous avons cherché à comprendre l’impact des différents protocoles de communications dans la vitesse de convergence au consensus.

Ces algorithmes distribués sont particulièrement utiles dans le cadre des réseaux de capteurs, où les agents sont des petites entités autonomes devant collaborer pour effectuer leur mission. Nous avons étudié comment de tels réseaux pourraient mettre en place l’algorithme Expectation-Maximization (EM) de façon distribuée [421] ou
encore une Analyse en Composantes Principales (ACP) [420], ou encore un algorithme de quantification adaptative [324].

Nos travaux ont été soutenus par des crédits de l’IMT (programme Futur et rupture) et par le CNRS (chaire).Signalons enfin que parmi les nombreuses publications de l’équipe sur ce thème, deux ont été faites dans IEEE Transactions on Signal Processing et une dans IEEE Transactions on Automatic Control.