Axes de recherches
Les travaux de l'équipe "Optimisation Combinatoire" du CEDRIC, de nature théorique et expérimentale, se classent actuellement en trois axes principaux : Programmation mathématique discrète, Tomographie discrète et planification et Optimisation dans les graphes.
Axe 1. Programmation mathématique
Cet axe s'attache à la résolution de problèmes modélisables par la programmation mathématique : problèmes de localisation et d'affectation, optimisation de fonctions quadratiques, partitionnement de graphes... Les méthodes de résolution s'appuient en particulier sur le calcul de bornes et l'utilisation de la programmation linéaire, semidéfinie, quadratique convexe, de méthodes de coupes polyédriques et de méthodes de convexification. Cet axe est divisé en trois thèmes : Etude de problèmes génériques, Modélisation et résolution de problèmes d'optimisation combinatoire par la programmation en variables mixtes, Application à des problèmes concrets particuliers.
Axe 2. Tomographie discrète et application
Cet axe s'attache à des problèmes de reconstruction (matrices, images, emplois du temps...). Il se divise en deux thèmes : Tomographie et Application à et la planification d'horaires de travail. Plus récemment, des liens entre certains problèmes de coloration et ceux de tomographie discrète ont été mis en lumière par l'équipe qui a proposé un cadre plus général permettant de traiter de manière unifiée ces deux classes de problèmes difficiles. Ces derniers travaux sont menés en collaboration avec l'EPFL.
Axe 3. Optimisation dans les graphes
Cet axe s'attache à la résolution de problèmes d'optimisation dans les graphes, et notamment des problèmes de routage, de multicoupe, de couplage et de coloration sous contraintes. L'étude menée porte à la fois sur la résolution exacte (en temps polynomial) de sous-problèmes particuliers (familles de graphes particulières) et sur la recherche d'algorithmes approchés efficaces pour les problèmes plus généraux. Cet axe se divise en deux thèmes : Multichemins, multiflots entiers et multicoupes, et Couplages et coloration d'arêtes sous contraintes.
Perspectives
Actuellement, l'un des objectifs de l'équipe est d'obtenir des résultats généraux sur l'optimisation quadratique en 0-1 et en nombres entiers. Pour cela, les approches différentes menées par plusieurs chercheurs de l'équipe sont comparées ou utilisées simultanément (relaxations linéaires et non-linéaires).
La résolution des problèmes de multiflots entiers n'en est qu'à ses débuts. Ces problèmes ont de très nombreuses applications. Les grilles, structure de graphes utilisés en particulier dans les VLSI, ainsi que les anneaux ont été particulièrement étudiés. Les compétences acquises sur le sujet dans l'équipe doivent permettre d'aborder les problèmes difficiles dans les graphes quelconques.
On rencontre des problèmes d'optimisation dans beaucoup de domaines de l'informatique. Une collaboration se met en place avec des chercheurs de l'équipe RSM pour l'optimisation du placement de copies de fichiers distribués sur lequel certains chercheurs de l'équipe ont déjà travaillé. D'autre part, les méthodes de marquage utilisées pour la sécurisation des bases de données nécessitent la résolution de grandes instances de problèmes d'optimisation combinatoire. Les échanges qui ont eu lieu à ce sujet avec l'équipe Vertigo ont permis d'identifier assez clairement le problème en terme d'optimisation combinatoire. Il s'agit d'un problème difficile et intéressant que les deux équipes vont tenter de résoudre.
A l'extérieur, l'équipe maintient des relations privilégiées avec France Télécom (recherche et développement), et des collaborations régulières (mais actuellement informelles) avec le Lamsade (Paris IX) et le LIPN (Paris XIII). L'équipe participe également à un projet en phase de démarrage LMI-SDP2 portant sur une nouvelle famille de relaxations semidéfinies en collaboration avec l'INRIA Grenoble.
Dans l'état actuel des connaissances de très nombreux problèmes d'optimisation combinatoire comportant quelques dizaines de variables sont impossibles à résoudre. L'équipe essaye de progresser dans la résolution pratique de ces problèmes difficiles. Des progrès théoriques et algorithmiques importants sont toujours nécessaires. La recherche d'algorithmes de résolution (en solutions exactes) permettant de traiter des problèmes de taille raisonnable, l'utilisation des méthodes approchées puis leur validation par calcul d'un majorant de l'écart entre la solution optimale et la solution approchée restent pour beaucoup de problèmes des enjeux importants. Les compétences acquises dans l'équipe continueront à être utilisées dans cette voie. Nous avons pu voir également l'importance de la modélisation choisie lors de l'étude de plusieurs problèmes particuliers : il s'agit maintenant de généraliser cet aspect de nos recherches.
