Axe 1.1

Affectation Quadratique

Le problème d’Affectation Quadratique consiste à trouver le placement optimal de n unités sur n sites de façon à minimiser un coût quadratique dépendant à la fois des distances inter-sites et des flux inter-unités. Ce problème a de très nombreuses applications pratiques tant en informatique qu’en productique, électronique ou architecture, mais se montre extrêmement difficile à résoudre. Ainsi, malgré 30 années de recherches, la taille des applications pouvant être résolue exactement demeure basse (autour de n = 30). L’équipe a depuis longtemps acquis une renommée internationale sur ce problème au travers d’algorithmes séquentiels ou parallèles.

En 2000, deux événements importants se sont produits aux Etats-Unis, accroissant la popularité de ce problème: l'un à l'Université de Pennsylvanie où Peter Hahn a réussi à résoudre l'instance Nugent de taille 25 avec une machine séquentielle au bout de quelques mois de calculs; l'autre au laboratoire national d'Argonne, où l'équipe Anstreicher et al. a résolu pour la première fois le problème Nugent de taille 30 en 7 jours sur une plate-forme composée de 2500 machines (projet MetaNEOS utilisant la plate-forme Globus).

Fort de notre expérience sur la parallélisation des algorithmes de type séparation et évaluation (Branch-and-Bound) et de notre connaissance de ce problème, nous avons établi plusieurs accords NSF de 2000 à 2005 avec Monique Guignard Spielberg et Peter Hahn (Wharton school, University of Pennsylvania) pour travailler sur un nouvel algorithme. La borne du QAP est obtenue à partir de la linéarisation du problème et après application d’une reformulation ou lifting appelé RLT. La méthode s’apparente à une Décomposition Lagrangienne itérée. Le second a consisté à utiliser la bibliothèque Bob++  développée par notre équipe pour le paralléliser (voir Axe 2)

.Nous avons amélioré la technique d’évaluation, les stratégies de branchement pour la méthode de Branch and Bound (B&B) sur chacun de ces problèmes avec A.Djerrah thésard coencadré avec VanDat Cung, professeur à Grenoble depuis 2003. Nous avons même optimisé à la compilation le calcul de ces évaluations faites en chaque nœud de l’arbre parcouru avec l’équipe ARPA Architecture de PRiSM.

Les résultats récents ont montré qu’un temps d’environ 7 heures était suffisant pour résoudre l'instance Nugent de taille 27 sur  Terranova (256 processeurs) avec le support d'exécution Athapascan/Kappi de l'Université de Grenoble. Nous poursuivrons l’étude de sa parallélisation à travers le projet ANR, CHOC

Automatisation des plans de traitement des tumeurs cancereuses par radiation interne

Le but de ce nouveau projet est d'apporter une aide à la décision à des médecins sur des problèmes difficiles touchant la santé publique, en les aidant à construire des plans de traitement plus efficaces et moins "destructeurs" pour le malade dans le cas du choix de l'emplacement et du dosage d'implants radioactifs en curiethérapie.

                La HDR curiethérapie à haut degré de radiation consiste à introduire temporairement dans le corps du patient par voie opératoire ou à travers une cavité  une source radioactive pour détruire la tumeur par irradiation. La source se déplace à travers un catheter (tubes étroits) et s’arrête à différents intervalles. Elle est en fait contrôlée par une machine programmée, un « remote afterloader », qui pousse la source radioactive à haut débit (Irridium Ir192) dans chaque catheter, un à la fois, en s’arrêtant à des positions calculées dites positions d’arrêt espacées par exemple de 0.25/1 mm de  et pour un temps prescrit. La distribution de dose peut donc être modulée grâce aux nombreuses positions d’arrêt en y laissant plus ou moins longtemps la source. Les doses finales reçues peuvent être évaluées avant de commencer tout traitement. Un autre avantage est qu’une fois la curithérapie terminée le patient n’est plus radioactif. Le traitement consiste alors en un petit nombre de séances (3 ou 10) séances de quelques minutes (10/15), une fois par semaine.

Plusieurs façons d’évaluer la dose distribuée co-existent. Un traitement est généralement considéré comme bon lorsqu’il délivre une dose suffisante pour détruire les tissus tumoraux sans sur dosage susceptibles d’entraîner des effets secondaires et tout en protégeant les organes à risque (comme le cerveau, la vessie, etc.) et les tissus sains. Nous avons étudié les problèmes liés aux différentes techniques de curiethérapie, en les classifiant et comparant les modèles d’optimisation utilisés.

Dans le cadre d’une application menée avec Gilbert Boisserie, de l’Unité de Physique du service de radiothérapie de l’hôpital de la Pitié-Salpétrière de Paris, pour un problème de traitement en curiethérapie HDR, nous avons conçu un logiciel graphique 3D capable de calculer la « meilleure » implantation des catheters dans lequel la source d’irridium va circuler, ainsi que les points et les temps d’arrêt de façon à respecter au mieux les contraintes cliniques de dosage fourni par le médecin. La méthode se fonde pour l’obtention des points et temps d’arrêt sur une modélisation par programmation linéaire continue résolue optimalement par un solver et sur une optimisation continue approchée pour améliorer le placement des catheters.

Cette étude a mené au logiciel Isodose 3D, dont une description plus détaillée est disponible sur cette page.

Filtres antispams

Ce travail s’inscrit dans les préoccupations actuelles concernant la sécurité des utilisateurs d’Internet, des industriels, des opérateurs de télécommunication. Certes de nombreux efforts ont été et sont déjà déployés pour faire face à ce qui est considéré comme un fléau mais il nous a paru intéressant de coupler et enrichir l’approche actuelle « statistique » à la lueur des techniques d’optimisation ou de Recherche Opérationnelle. L'enjeu est de briser le modèle économique sur lequel repose le spam. Moins les filtres demanderont d'intervention utilisateur, plus ils seront utilisés, et moins les campagnes de spam seront efficaces, se révélant à terme non viables économiquement pour les spammeurs.

Nous avons  actuellement amélioré  la technique la plus populaire dans le filtrage du spam durant les cinq dernières années, le classifieur bayésien semi-naïf,  fondé sur une analyse statistique contenu du message et en particulier des attributs (occurrence de mots, d'expression, balises, etc.). Nous le composons avec une recherche fondée sur les réseaux sociaux, analysant quant à elle la topologie du graphe des communications de l'utilisateur pour déterminer si un message donné provient ou non d'un réseau social, par opposition aux réseaux de spam.

Nous travaillons actuellement sur l’optimisation de la composition de filtres pour s’affranchir totalement du problème des faux positifs. Nous comptons étendre ces techniques au filtrage d’images ou de SMS-MT envoyés aux abonnés d’un réseau par les autres réseaux.

Coupes dans les softwares de programmation en nombres entiers

 

Ce travail est en premier lieu orienté vers l'étude et l'analyse critique des coupes en vue de leur utilisation dans les softwares commerciaux (XPRESS) ou développés par RTE (Réseau Transport Electrique) pour la résolution de programmes linéaires en nombres entiers, modélisant des problèmes de transport d’electricité.

Une première hiérarchisation entre les coupes proposées dans la littérature a été construite et le choix ainsi que le moment de leur introduction dans l’arbre Branch and Bound y est étudié pour des problèmes avec des variables binaires (Gomory, MIR, Lift and Project) qui peuvent être intéressantes.

Il s’agit ensuite de développer et tester Ces méthodes de coupes ont été développées et testées avec le solveur Xpress Mosel, et leur intégration au solveur de programmation linéaire mixte développé par RTE est envisagée.

Une grande partie de ce travail a été intégré dans la bibliothèque Glop

 Imprimer 

DMC Firewall is developed by Dean Marshall Consultancy Ltd