Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes

Romain CAMPIGOTTO : Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes : le problème du Vertex Cover.

Martine Caccioppoli — 2012-04-04T11:47:16Z

6 décembre 2011, à l'université d'Evry

De nos jours, de nombreux domaines tels que la biologie, la météorologie, les finances... produisent de très grandes quantités de données. Ces données sont collectées/générées par une source (un laboratoire ou une entreprise) qui les stocke bien souvent sur des entrepôts de données. Cette source peut ouvrir un accès à plusieurs partenaires extérieurs. Mais, pour éviter que les données soient corrompues par les manipulations de ces partenaires, elles ne doivent être accessibles qu'en lecture seule.

Les travaux de thèse portent sur l'étude de problèmes d'optimisation dans un contexte bien particulier, celui du traitement des grandes instances de données sur une seule machine, dotée de capacités mémoire standard.
Ce contexte fait l'objet de plusieurs contraintes spécifiques, synthétisées ci-dessous.

1/ Les données en entrée ne doivent pas être modifiées : leur intégrité doit être préservée.
2/ L'unité de traitement dispose d'un espace mémoire restreint (par rapport à la grande taille de l'instance à traiter).
3/ La solution doit être envoyée "à la volée", c'est-à-dire pièce par pièce, au fur et à mesure qu'elle est calculée durant le traitement.
La contrainte 3 provient du fait que dans de nombreux cas, la solution peut être aussi grosse que l'instance en entrée. Elle ne peut donc pas non plus tenir entièrement en mémoire.

Nous nous intéressons à un problème NP-complet bien connu, celui du Vertex Cover. Il s'agit de trouver une couverture de taille minimale dans un graphe, c'est-à-dire un plus petit sous-ensemble de sommets tel que chaque arête du graphe possède au moins une extrémité dans ce sous-ensemble.

Nous avons étudié 3 heuristiques adaptées au traitement de gros graphes pour le problème du Vertex Cover. En effet, elles respectent les 3 contraintes énumérées ci-dessus et elles ne nécessitent pratiquement pas d'espace mémoire sur l'unité de traitement. Nous avons analysé et comparé en pire cas et en moyenne leurs complexités (en nombre de requêtes) et la qualité des solutions qu'elles produisent, en donnant notamment, pour chacune des 3, les formules exactes exprimant la taille moyenne des solutions qu'elles retournent et le nombre moyen de requêtes qu'elles effectuent, dans le but de les étudier de manière analytique sur différentes familles de graphe.

Nous avons ensuite assoupli la contrainte 2, en autorisant un espace mémoire de n bits, ce qui nous a permis d'adapter d'autres algorithmes. Nous avons montré qu'avec strictement moins de n bits, ces algorithmes pouvaient être très mauvais.

Par la suite, nous avons mené une étude expérimentale sur de très gros graphes (de l'ordre de plusieurs milliards de sommets et d'arêtes, soit plus de 1 To sur disque pour les plus gros). Nous avons implémenté les algorithmes que nous avons étudiés et nous les avons exécutés sur plusieurs instances (des graphes que nous avons générés "à la volée").

Cette étude nous a permis de montrer qu'en pratique, ils étaient bien adaptés pour traiter de grands graphes (leurs temps d'exécution ne dépassent pas une dizaine d'heures). Cependant, nous avons observé que ceux qui produisaient les meilleures solutions pouvaient atteindre leurs limites (on ne peut plus les exécuter lorsque la taille du graphe est trop importante).

Jury :
Matthieu Latapy (Directeur de Recherche CNRS au LIP6) : Président du jury
Dominique Barth (Professeur à l'Université de Versailles) : Rapporteur
Pascal Berthomé (Professeur à l'ENSI de Bourges) : Rapporteur
Bruno Escoffier (Maître de Conférences à l'Université Paris-Dauphine) : Examinateur
Christian Laforest (Professeur à l'Université Blaise Pascal, Clermont-Ferrand) : Co-directeur de thèse
Eric Angel (Professeur à l'Université d'Évry-Val d'Essonne) : Directeur de thèse.

Pascal GIRODET : Conception et modélisation d'un système de mesure de la force d ?impact dans les Sports de Combat et les Arts Martiaux.

Martine Caccioppoli — 2012-03-26T07:23:59Z

Mardi 27 mars 2012 - 14 h 30 - Amphi 2 du pôle commun CUST-ISIMA

Soutenance à huis-clos

L'objectif de cette thèse était d'évaluer la force d ?impact dans des conditions proches de la pratique des Sports de Combat et des Arts Martiaux (SCAM) à l'aide d'un ergomètre spécifiquement conçu dans le cadre de ces travaux. Les mesures dynamiques ont été associées à des mesures cinématiques 3D à haute vitesse afin de caractériser les gestes de frappe de quatre boxeurs en situation d'entraînement, et d'en identifier les paramètres d'optimisation gamme des énergies cinétiques pic et incidente du membre supérieur, gamme des pics de force d ?impact, et forces intra-articulaires au poignet, au coude et à l'épaule, calculées par dynamique inverse. Parallèlement, l ?évaluation mécanique de quelques protections de boxe française (gants et bandages) et de karaté (gants, protège-pieds et protèges-tibias) a montré que le test défini par la norme NF EN 13277-2 était insuffisant pour caractériser leurs propriétés amortissantes. Les résultats des mesures en situation et en laboratoire ont mis en évidence la qualité discutable de certains gants de boxe française et l'absence d ?effet protecteur des bandages. La Fédération Française de Boxe Française (FFSBFDA) doit encore tirer toutes les conclusions de ces résultats. Les résultats des protections de karaté ont permis à la Fédération Française de Karaté (FFKDA) d'en définir les caractéristiques souhaitables, qui ont été approuvées par la Fédération Mondiale de Karaté (WKF). Au-delà de ces conséquences pratiques, la cible-ergomètre conçue, fabriquée et mise en ?uvre dans cette thèse, et le modèle mécanique associé présentent des avantages expérimentaux et ergonomiques qui ouvrent des perspectives d ?évaluation de la force d'impact de nombreuses techniques de frappe utilisées dans les Sports de Combat et les Arts Martiaux.

JURY :

Floren COLLOUD : Maître de Conférences, Institut Pprime - Université de Poitiers (Examinateur)

Jacques CREMIEUX : Professeur des Universités, Université du Sud Toulon ? Var (Rapporteur)

Raphaël DUMAS : Maître de Conférences - HDR, LBMC - Université de Lyon (Rapporteur)

Kun Mean HOU : Professeur des Universités, LIMOS - Clermont Université (Correspondant universitaire)

Patrick LACOUTURE : Professeur des Universités, Institut Pprime - Université de Poitiers (Directeur de thèse)

Philippe VASLIN : Maître de Conférences, LIMOS - Clermont Université (Co-encadrant) .

Heitor LIBERALINO : Problèmes de Production avec Transport des Composants.

Martine Caccioppoli — 2012-03-15T13:33:10Z

Jeudi 22 Mars à 11h00 - Salle E005 - ISIMA

Dans ce travail nous considérons des problèmes de planification de production sur plusieurs sites avec transport de produits entre ces sites. L'objectif est de synchroniser les deux problème (planification et transport) et de construire une solution globale. Le système de production sur chaque site est modélisé comme un problème de Capacitated Lot-Sizing où nous travaillons avec stock et ressources. Le transport de produits entre les sites se ramène à une version simplifiée du Vehicle Routing Problem où le temps est discrétisé. D'abord nous proposons un modèle linéaire en nombres entiers que nous appelons le « Lot-Sizing and Vehicle Routing Problem » (LSVRP). Puis nous présentons deux cas particuliers : le Single-item LSVRP (SLSVRP) et le Single-level LSVRP (1-LSVRP). Les problèmes sont traités ici par six heuristiques que nous avons développé. Quatre de ces méthodes sont des heuristiques qui utilisent la programmation en nombres entiers et prennent en compte la relaxation linéaire de quelques variables du problème. Elles s'appuient sur l'exploration partielle de l'arbre de décision et la fixation de variables. Les deux autres

sont spécifiques pour les cas particuliers. La première, qui traite le S-LSVRP, est basée sur la propagation des ordres de production sur chaque site. Puis à chaque itération elle calcule le plan de transport compatible et essaie d'améliorer la solution en modifiant la production sur les sites. L'autre méthode consiste en une relaxation lagrangienne qui travaille sur une modélisation du 1-LSVRP en un problème de flot. Des résultats numériques et des analyses sont présentés pour évaluer l'efficacité de ces heuristiques.

Le jury sera composé des membres suivants :

Président :
Maître de Conférences Safia KEDAD-SIDHOUM, Université Pierre et Marie Curie

Rapporteurs :
Maître de Conférences Mauricio C. DE SOUZA, Universidade Federal de Minas Gerais, Belo Horizonte, Brésil
Professeur Alexandre DOLGUI, Ecole Nationale Supérieure des Mines de Saint-Etienne
Professeur Aziz MOUKRIM, Université de Technologie de Compiègne

Responsables :
Professeur Alain QUILLIOT, Université Blaise Pascal, LIMOS
Maître de Conférences Christophe DUHAMEL, Université de Technologie de Troyes.

Alexandre-Xavier MARTINS : Métaheuristiques et modélisation du problème de routage et affectation de longueurs d'ondes pour les réseaux de communications optiques.

Martine Caccioppoli — 2012-03-13T09:59:56Z

- Thèses soutenues en 2011-2012 / Thèses, Thèses

Pierre Marquis, Professeur, CRIL UMR CNRS (Université d'Artois) :

Martine Caccioppoli — 2012-03-12T08:11:36Z

Jeudi 28 juin 2012 - 14 h 00 -Amphi Bruno Garcia - ISIMA - Séminaires en cours ou à venir / Séminaires, Séminaires

Michaël Rao (Chargé de recherche CNRS au LIP, ENS de Lyon) : Domination dans les grilles

Martine Caccioppoli — 2012-03-12T07:24:00Z

Jeudi 21 juin 2012 - 14 h 00

Chang a conjecturé en 1994 que la taille minimum d'un ensemble dominant dans une grille n x m, avec n<=m<=16, est la partie entière de $(n+2)(m+2)/5 - 4$. Je montrerai comment prouver ce résultat, en transformant le problème en une minimisation de ``pertes'', puis en utilisant des matrices de transfert dans l'algèbre tropicale. Ces techniques de matrices de transfert sont en fait applicables à d'autres paramètres, et à d'autres graphes. Puis je parlerai des problèmes soulevés lorsqu'on cherche à compter les ensembles dans une grille.
(Collaboration avec D. Gonçalves, A. Pinlou et S. Thomassé).

Jérôme Euzenat, Directeur de recherches, INRIA & LIG (Grenoble) : Quelques questions sur les réseaux d'ontologies

Martine Caccioppoli — 2012-03-11T08:13:00Z

Jeudi 14 juin 2012 - 14 h 00 - Amphi Bruno Garcia - ISIMA

Les réseaux d'ontologies sont un artefact du web sémantique : un ensemble d'ontologies liées par des alignements.
Ils sont intéressant à étudier en tant que tels, en premier lieu parce que leur donner une sémantique permet de savoir comment interpréter la nature des liens qui lient les ontologies. On considèrera plusieurs sémantiques et retiendra ce qu'elles ont en commun. Disposer d'une sémantique permet à son tour de définir quelques notions classiques telles que l'inconsistance ou la subsomption entre réseaux. Ces notions peuvent à leur tour être utilisées pour définir des opérations plus larges permettant de manipuler ces réseaux (cloture, révision) et le les faire évoluer suite à l'évolution du contexte dans lequel ils évoluent. Cet exposé présentera certaines de ces notions
ainsi que quelques problèmes que leur définition pose.

Philippe PREUX (INRIA)

Martine Caccioppoli — 2012-03-10T07:14:00Z

Jeudi 7 juin 2012 - 14 h 00 - Amphi Bruno Garcia - ISIMA - Séminaires en cours ou à venir / Séminaires, Séminaires

Stéphane Lallich, Professeur à l'Université de Lyon 2 (Laboratoire Eric)

Martine Caccioppoli — 2012-03-09T07:53:19Z

Jeudi 31 mai 2012 - 14 h 00 - Amphi Bruno Garcia - ISIMA - Séminaires en cours ou à venir / Séminaires, Séminaires

Pascal GIRODET : Conception et modélisation d'un système de mesure de la force d'impact dans les Sports de Combat et les Arts Martiaux.

Martine Caccioppoli — 2012-03-06T09:30:59Z

Mardi 27 mars 2012 à 14h30 - Pôle Commun - Amphi 2

L'objectif de cette thèse était d'évaluer la force d'impact dans des conditions proches de la pratique des Sports de Combat et des Arts Martiaux (SCAM) à l'aide d'un ergomètre composé d'un bloccible instrumenté avec un accéléromètre et un dynamomètre, et monté sur une lame flexible fixée verticalement sur le sol. La force d'impact a été calculée à partir des trois composantes mesurées par le dynamomètre, d'une part, et à partir de l'accélération du bloc-cible, grâce à un modèle mécanique original, d'autre part. Les mesures dynamiques ont été associées à des mesures cinématiques 3D à haute vitesse afin de caractériser les gestes de frappe de quatre boxeurs en situation d'entraînement, et d'en identifier les paramètres d'optimisation : gamme des énergies cinétiques pic et incidente du membre supérieur, gamme des pics de force d'impact, et forces intra-articulaires au poignet, au coude et à l'épaule, calculées par dynamique inverse. Parallèlement, l'évaluation mécanique de quelques protections de boxe française (gants et bandages) et de karaté (gants, protège-pieds et protèges-tibias) a montré que le test défini par la norme NF EN 13277-2 était insuffisant pour caractériser leurs propriétés amortissantes. Les résultats des mesures en situation et en laboratoire ont mis en évidence la qualité discutable de certains gants de boxe française et l'absence d'effet protecteur des bandages. La Fédération Française de Boxe Française (FFSBFDA) doit encore tirer toutes les conclusions de ces résultats. Les résultats des protections de karaté ont permis à la Fédération Française de Karaté (FFKDA) d'en définir les caractéristiques souhaitables, qui ont été approuvées par la Fédération Mondiale de Karaté (WKF). Au-delà de ces conséquences pratiques, la cible-ergomètre conçue, fabriquée et mise en oeuvre dans cette thèse, et le modèle mécanique associé présentent des avantages expérimentaux et ergonomiques qui ouvrent des perspectives d'évaluation de la force d'impact de nombreuses techniques de frappe utilisées dans les Sports de Combat et les Arts Martiaux.
Mots clés : Force d'impact, Ergomètre, Sports de Combat, Arts Martiaux, Biomécanique.

Jury :

Floren COLLOUD : Maître de Conférences Université de Poitiers ENSMA, Examinateur

Jacques CREMIEUX : Professeur des Universités, Université du Sud Toulon-Var Rapporteur

Raphaël DUMAS : Maitre de Conférences, Université Claude Bernard – Lyon1, Rapporteur

Kun Mean HOU : Professeur des Universités, Université Blaise Pascal – Clermont Université, Correspondant local

Patrick LACOUTURE : Professeur des Universités, Université de Poitiers, Directeur de thèse

Philippe VASLIN : Maître de Conférences, Université Blaise Pascal – Clermont Université, Co-directeur de thèse.