Optimisation dans les graphes. Ce premier axe se focalise sur les problèmes qui se modélisent dans les graphes ou hypergraphes. Nous traitons aussi bien les algorithmes pour des problèmes polynomiaux tels que le flot maximum et le plus court chemin, que les études d'ordre structurel sur les espaces de solutions, par exemple dans le cadre de l'approche polyédrale. Ces éléments de structure permettent d'obtenir de nouvelles formulations des instances, ainsi qu'une caractérisation plus fine de leur complexité. De telles caractérisations permettent ensuite de concevoir des algorithmes de résolution plus efficaces, qu'ils soient exacts ou approchés avec garantie de performance.
Programmation mathématique. Ce deuxième axe se fédère autour de la résolution des problèmes d'optimisation combinatoire à travers la programmation mathématique. Nous y abordons la résolution exacte et approchée de ces problèmes, par la conception de différents outils et approches. Parmi ces approches figurent les schémas de génération de contraintes et de génération de colonnes, ainsi que les méthodes de décomposition et de relaxation. Nous abordons également la résolution des problèmes par des modèles non linéaires, les méthodes de réoptimisation et celles de type matheuristique.
Algorithmes, logiciels et architectures distribués . Ce troisième axe rassemble notre expertise dans un environnement distribué. Nous travaillons plutôt à l'intersection de trois domaines (i.e. algorithmes, logiciel et architecture). L'algorithmique concerne ici le parallélisme pour des bibliothèques numériques, ou le calcul des propriétés de tolérance aux fautes dans des grands graphes. Concernant l'aspect logiciel nous traitons de langages de programmation parallèles à mémoire partagée distribuée et de la résilience dans le "Cloud". Enfin quand nous repensons en termes d'outils Web les interactions dans une grille et quand nous développons une architecture modulaire pour permettre d'expérimenter des algorithmes au sein d'un support d'exécution on parle d'architecture logicielle.
Ces trois axes sont intimement liés : les algorithmes exacts peuvent s'appuyer sur une borne primale dont la garantie de qualité aura été préalablement établie ou sur des contraintes valides dont la séparation aura été démontrée polynomiale ; inversement, un algorithme d'approximation peut s'appuyer sur une relaxation linéaire ou quadratique. De façon similaire, l'étude des propriétés de graphes particuliers et la conception d'algorithmes distribués permettant de les construire sont en particulier motivées par le contexte spécifique des architectures distribuées à large échelle.
Taille du Laboratoire : 191 membres (permanents + doctorants).
Taille de l'équipe R.O. : 4 PR, 10 MCF, 30 membres en tout (dont doctorants, post-doc, ingénieurs).
Responsable : Frédéric Roupin
Mots clés : Optimisation Combinatoire, Optimisation dans les graphes, Programmation mathématique, Complexité, Algorithmes logiciels et architectures distribués
Site internet : http://lipn.univ-paris13.fr/fr/aoc-2
Contact équipe : roupin@lipn.fr
NB : Les pages équipes vont être enrichies avec de nouvelles informations très bientôt...
Si vous souhaitez nous envoyer des corrections ou inscrire votre équipe, cliquez ici pour plus de détails.
