Jing Chang, doctorante au sein de l’équipe ReV, soutiandra sa thèse intitulée « The risk assessment of work related Musculoskeletal disorders based on OpenSim »
vendredi 30 novembre à 10h, sur le site de Centrale Nantes, dans l‘amphi du bâtiment S.
Jury : Fouad Bennis (directeur), Damien Chablat (co directeur), Georges Dumont (Rapporteur, INSA Rennes), Gérard Posson (IUT Bourges, rapporteur), Laurence Cheze (LBMC), Liang Ma (Université Tsinghua),
Houda Harbaoui, doctorante au sein de l’équipe SLP, soutiendra sa thèse intitulée « Ordonnancement d’un système de production industriel complexe: flow shop hybride avec des machines dédiées soumis à différentes contraintes temporelles » / « Scheduling of a complex industrial production system: Hybrid flow shop with dedicated machines and different time constraints »
vendredi 14 décembre 2018 à 14h00, dans l’amphi Besse de l’IMT-A.
Jury : Odile Bellenguez Morineau (directrice thèse), Mohamed Haouari (co directeur, U. Norfolk), Safia Kedad Sidhoum (CNAM Paris), Anis Gharbi (Rapporteur TBS Tunis), Vincent T’Kindt (Univ Tours), Najoua Drifi (ENIT Tunis),Soulef Khalfallah (ISG Sousse)
Résumé :
L’accroissement des profits, à travers l’amélioration de la productivité et la réduction des pertes de matière, représente un objectif primordial pour les entreprises industrielles. Dans cette thèse, nous nous intéressons à la résolution d’un problème industriel complexe réel avec des contraintes de temps. Nous nous sommes intéressés, tout d’abord, à un objectif principal, soit la minimisation des dates de fin de production, suivi d’un objectif secondaire qui est la minimisation des quantités de déchets non recyclables.
Dans un premier temps, nous avons modélisé le problème par des modèles mathématiques, que nous avons résolu à l’aide d’un solveur. Dans un second temps, nous avons proposé une méthode approchée en forme d’algorithmes évolutionnistes. Cette méthode est appliquée aux deux objectifs mentionnés ci-dessus séparément. Une troisième méthode est ensuite appliquée à l’objectif principal, à savoir un algorithme de séparation et évaluation. Nous avons testé les algorithmes proposés sur des instances inspirées d’un cas réel ; issues d’une entreprise du secteur agroalimentaire et sur des instances inspirées de la littérature.
Mots-clés : Ordonnancement, contraintes temporelles, méta-heuristique, flow shop hybride, MIP
***********
Abstract:
Increasing profits, through the improvement of productivity and the reduction of material waste, is a primary objective for industrial companies. In this thesis, we are interested in solving a real complex industrial problem with time constraints. We were interested; first of all, in a main objective, namely the minimization of the completion time (Cmax), followed by a secondary objective which is the minimization of the quantities of non-recyclable waste. At first we formulated the problem by mathematical models, which we solved using a solver. In a second step, we proposed an approximate method in the form of a evolutionary algorithms. Both methods were applied to the two objectives mentioned above seperatly. A third method was then applied only to the main objective, namely a Branch and Bound algorithm. We tested the proposed algorithms on instances inspired from a real case; from an agri-food business, and also on instances inspired from the literature.
Keywords: Scheduling, temporal constraints, metaheuristic, Hybrid Ffow shop, MIP
Misbah Razzaq, doctorante au sein de l’équipe COMBI, soutiendra sa thèse intitulée « Integrating Phosphoproteomic Time Series Data into Prior Knowledge Networks » / « Intégration de données de séries temporelles phosphoprotéomiques dans des réseaux de connaissances antérieurs »
mercredi 5 décembre 2018 à 14h dans l’amphi du bâtiment S sur le site de Centrale Nantes.
Jury : Jérémie Bourdon (directeur de thèse), Carito Guziolowski (co encadrante), Thomas Sauter (rapporteur, Université du Luxembourg), Céline Rouveirol (rapporteur, Institut Galilée), Frédéric Saubion (LERIA), Sara-June Dunn (Microsoft Research, Cambridge), Sabine Peres (Université Paris Sud)
Abstract: Traditional canonical signaling pathways help to understand overall signaling processes inside the cell. Large scale phosphoproteomic data provide insight into alterations among different proteins under different experimental settings. Our goal is to combine the traditional signaling networks with complex phosphoproteomic time-series data in order to unravel cell specific signaling networks. On the application side, we apply and improve a caspo time series method conceived to integrate time series phosphoproteomic data into protein signaling networks. We use a large-scale real case study from the HPN-DREAM Breast Cancer challenge.
We infer a family of Boolean models from multiple perturbation time series data of four breast cancer cell lines given a prior protein signaling network. The obtained results are comparable to the top performing teams of the HPN-DREAM challenge. We also discovered that the similar models are clustered together in the solutions space. On the computational side, we improved the method to discover diverse solutions and improve the computational time.
Keywords: signaling networks, logic programming, model checking, cell lines
*********
Résumé : Les voies de signalisation canoniques traditionnelles aident à comprendre l’ensemble des processus de signalisation à l’intérieur de la cellule. Les données phosphoprotéomiques à grande échelle donnent un aperçu des altérations entre différentes protéines dans différents contextes expérimentaux. Notre objectif est de combiner les réseaux de signalisation traditionnels avec des données de séries temporelles phosphoprotéomiques complexes afin de démêler les réseaux de signalisation spécifiques aux cellules. Côté application, nous appliquons et améliorons une méthode de séries temporelles caspo conçue pour intégrer des données phosphoprotéomiques de séries temporelles dans des réseaux de signalisation de protéines. Nous utilisons une étude de cas réel à grande échelle tirée du défi HPN-DREAM Breast Cancer.
Nous déduisons une famille de modèles booléens à partir de données de séries temporelles de perturbations multiples de quatre lignées cellulaires de cancer du sein, compte tenu d’un réseau de signalisation protéique antérieur. Les résultats obtenus sont comparables aux équipes les plus performantes du challenge HPN-DREAM. Nous avons découvert que les modèles similaires sont regroupés dans l’espace de solutions. Du côté informatique, nous avons amélioré la méthode pour découvrir diverses solutions et améliorer le temps de calcul.
Adeline Granet, doctorante au sein de l’équipe TALN soutiendra sa thèse intitulée « Extraction d’information dans des documents manuscrits anciens » / « Extracting information in old handwritten documents »
mercredi 12 décembre à 14h, dans l’amphi du Bâtiment 34sur le site de l’UFR Sciences.
Jury : Emmanuel Morin (directeur de thèse), Harold Mouchère (co-encadrant), Frédéric Béchet (rapporteur, U Marseille), Antoine Doucet (Rapporteur, U la Rochelle), Clément Chatelain (INSA Rouen), Solen Quiniou
Résumé : La tâche d’exploration dans des ressources inexploitées mais nouvellement numérisées, afin d’y trouver des informations pertinentes, est complexifiée par la quantité de
ressources disponibles. Grâce au projet ANR CIRESFI, la ressource la plus importante, pour la Comédie-Italienne du XVIIIe siècle, est un ensemble de registres comptables constituée de 28 000 pages. L’extraction d’informations est un processus long et complexe qui demande une expertise à chaque étape : détection et segmentation, extraction de caractéristiques, reconnaissance d’écriture manuscrite. Les systèmes à base de réseaux de neurones profonds dominent dans l’ensemble ces approches. Le problème majeur est qu’ils nécessitent d’avoir une grande quantité de données pour réaliser leur apprentissage.
Cependant, les registres de la Comédie-Italienne ne possèdent pas de vérité terrain. Pour palier ce manque de données, nous explorons des approches pouvant opérer un apprentissage par transfert de connaissance. Cela signifie utiliser un ensemble de données déjà étiquetées et disponibles, possédant un minimum de points communs avec nos données pour entraîner les systèmes, pour ensuite les appliquer sur nos données. L’ensemble de nos expérimentations nous ont montré la difficulté de réaliser cette tâche, chaque choix à chaque étape ayant un impact fort sur la suite du système. Nous convergeons vers une solution séparant le modèle optique du modèle de langage afin de réaliser un apprentissage indépendant avec différents types de ressources disponibles et se rejoignant grâce à une projection de l’ensemble des informations dans un espace commun non-latent
Mots clés : Reconnaissance d’écriture manuscrite, Apprentissage par transfert de connaissance, Réseaux de neurones, Documents historiques, Modèle optique, Modèle linguistique
********
Abstract: Exploring unexploited but newly digitized resources to find relevant information is a complicated task due to the amount of available resources. Thanks to the ANR project CIRESFI, the most important resource for the Italian Comedy of the 18th century, is a set of accounting registers consisting of 28,000 pages. Information retrieval is a long and complex process that requires expertise at every step: detection and segmentation in paragraphs, lines or words, features extraction, handwriting recognition. Systems based on deep neural networks dominate these approaches. The major issue is the need of a large amount of data to achieve their learning.
However, the registers of the Italian Comedy have no ground truth. To overcome this lack of data, we explore approaches that involving transfer learning. That means using heterogeneous labeled and available data, with at least one common feature with our data to drive the systems, and then applying them to our data. All of our experiments have shown us the difficulty of carrying out this task, each choice at each stage having a strong impact on the rest of the system. We converge on a solution separating the optical model from the language model in order to achieve independent learning with different available resources and joining together thanks to a projection of the information into a non-latent common space.
Keywords: Handwriting recognition, Transfer learning, Neural network, Historical documents, Optical model, Linguistic model
Simon Boulier, doctorant au sein de l’équipe Gallinette, soutiendra sa thèse intitulée « extending type Theory with Syntactic Models »
jeudi 29 novembre 2018 à 14h00, dans l’amphi Blaise Pascale, à l’IMT Atlantique.
Jury : Nicolas Tabareau (dir thèse), Thierry Coquand (Université de Gothenburg, rapporteur), Hugo Herbelin (laboratoire IRIF PPS, rapporteur), Assia Mahboubi, Ambrus Kaposi Eötvös Lorand University Hongrie), Pierre Cointe
Tianyu Wang, doctorant au sein de l’équipe SLP, soutiendra sa thèse intitulée « Parallel machine scheduling with precedence constraints »
vendredi 5 octobre à 14h à Centrale Nantes dans l’amphithéâtre S.
Jury : Olivier Henri Roux (Professeur, Centrale Nantes), Odile Bellenguez-Morineau (Maitre Assistant HDR, IMT Atlantique), Christoph Dürr (Directeur de recherche CNRS, Sorbonne Université LIP6), Julien Moncel (Maitre de conférences, HDR IUT ROADEZ), André Rossi (Professeur Université d’Angers), Pierre Lemaire (Maitre de conférences, Grenoble INP).
Résumé :
Nous considérons une famille des problèmes d’ordonnancement avec machine parallèle identique et contraintes de précédences. Ce champ de recherche fait l’objet de nombreuses études. Malgré tout, la complexité de ces problèmes varie selon de nombreux paramètres, notamment le type de graphe de précédence ou le critère retenu. De plus, il existe encore de nombreux problèmes ouverts. Nous étudions certains de ces problèmes dans cette thèse. Nous montrons notamment que le problème ouvert avec tâches de durée unitaires et graphe de précédence de type in-tree est NP-complet. Puis, nous prouvons que le problème avec graphe de précédence de type level-order est NP-complet aussi. La preuve est ensuite étendue à des problèmes connexes. Par la suite, on améliore un algorithme exponentiel pour un problème spécifique qui est NP-complet. Enfin, nous proposons un modèle linéaire pour le problème avec contraintes de précédence quelconque, améliorant aussi les résultats de littérature.
**********
Abstract:
The main problem studied in this thesis is that of parallel machine scheduling with precedence constraints. The complexity depends on the shape that the precedence graph takes and the objective function. We prove that one minimum-open problem of scheduling equal-processing-time jobs which subject to in-tree precedence constrains is NP-complete while minimizing the total competition time. Then, we prove that the open problem of scheduling level-order precedence constrains is NP-complete too. We adapted the second proof to other scheduling problems as well. On the other hand, we improved an exponential algorithm designed for a specific NP-hard problem. At the end, we propose a linear programming model for the general scheduling problem with arbitrary precedence constraints and processing-time. We adapt the existing models which are originally designed for other scheduling prob
Julien Fradin, doctorant au sein de l’équipe COMBI, soutiendra sa thèse intitulée « Graphes complexes en biologie : problèmes, algorithmes et évaluation »
mardi 4 décembre à 10h30 dans l’amphi du bâtiment 34, sur le site de la Faculté des Sciences.
Jury de thèse : Guillaume Fertin (Directeur de thèse), Géraldine Jean (co encadrante), Ioan Todinca (Rapporteur, LIFO), Annie Château (Rapporteur, U Montpellier 2 – MAB), Michel Habib (U Paris Diderot, IRIF), Florian Sikora (U Paris Dauphine, LAMSADE, Damien Eveillard (Invité)
Résumé :
Afin de mieux comprendre le fonctionnement d’un système biologique, il est nécessaire d’étudier les interactions entre les différentes entités qui le composent. Pour cela, on peut modéliser ces réseaux d’interactions biologiques sous la forme de graphes dont les sommets sont colorés. Une problématique commune consiste alors à rechercher un sous-graphe
d’intérêt dans ces graphes pouvant comporter des milliers de sommets et d’arêtes. Dans ce manuscrit, on s’intéresse à deux problèmes conçus pour répondre à cette problématique. On présente tout d’abord un état de l’art sur le problème GRAPH MOTIF, pour lequel il existe une large littérature algorithmique, puis on réalise une étude algorithmique approfondie du problème MAXIMUM COLORFUL ARBORESCENCE.
Le problème MAXIMUM COLORFUL ARBORESCENCE est une redéfinition plus précise d’un problème de la littérature qui avait été introduit dans le but de déterminer de novo la formule moléculaire de petites molécules inconnues. Alors que MAXIMUM COLORFUL ARBORESCENCE est, tout comme le problème original, algorithmiquement difficile à résoudre même dans des classes d’arbres très contraints, cette nouvelle définition nous permet ainsi d’obtenir de nouveaux algorithmes d’approximation dans ces mêmes arbres
contraints et même de trouver une nouvelle classe de graphes dans laquelle MAXIMUM COLORFUL ARBORESCENCE se résout en temps polynomial. On montre également des résultats de complexité paramétrée pour ce nouveau problème, qu’on compare ensuite à ceux de la littérature pour le problème original sur des instances issues de données biologiques.
Mots-clés : Bioinformatique, Graphes, Complexité paramétrée, Approximation
***********
Abstract:
In order to better understand how a biological system works, it is necessary to study the interactions between the different entities that compose it. To do this, we can model these biological interaction networks with graphs whose vertices are colored. A standard problem then consists in searching for a subgraph of interest in these graphs, which can include thousands of vertices and edges. In this manuscript, we are interested in two problems designed to address this issue. First of all, we present a state of the art on the GRAPH MOTIF problem, for which there exists a large algorithmic literature, then we carry out an in-depth algorithmic study of the MAXIMUM COLORFUL ARBORESCENCE problem.
The MAXIMUM COLORFUL ARBORESCENCE problem is a more precise redefinition of a problem in the literature that had been introduced to determine de novo the molecular formula of unknown small molecules. While MAXIMUM COLORFUL ARBORESCENCE is, like the original problem, algorithmically difficult to solve even in very constrained tree classes, this new definition allows us to obtain new approximation algorithms in these same constrained trees. It even allows us to find a new graph class in which MAXIMUM COLORFUL ARBORESCENCE is solved in polynomial time. We also show parameterized complexity results for this new problem, which we then compare to those in the
literature for the original problem on instances from biological data.
Keywords: Bioinformatics, Graphs, Parameterized complexity, Approximation
Tarek Benkhelif, doctorant au sein de l’équipe DUKe, soutiendra sa thèse intitulée « Publication de données individuelles respectueuse de la vie privée : Une démarche fondée sur le co-clustering » / « Privacy preserving microdata publishing »
mardi 27 novembre à 14h, dans l’amphi 2 du bâtiment IRESTE à Polytech.
Jury : Marc Gelgon (directeur), Guillaume Raschia (co directeur), Benjamin Nguyen (Rapporteur, INSA Centre Val de Loire), Christophe Rosenberger (Rapporteur, ENSI CAEN), Pierre Gancarski (UNISTRA), Maryline Laurent (Telecom Sud Paris), Matthieu Grall (invité, CNIL), Françoise FESSANT (Orange Labs Lannion, invitée)
Résumé :
Il y a une forte demande économique et citoyenne pour l’ouverture des données individuelles. Cependant, la publication de telles données représente un risque pour les individus
qui y sont représentés. Cette thèse s’intéresse à la problématique de l’anonymisation de tables de données multidimensionnelles contenant des données individuelles dans un objectif de publication.
On se concentrera plus particulièrement sur deux familles d’approches pour l’anonymisation: la première vise à fondre chaque individu dans un groupe d’individus, la deuxième est basée sur l’ajout d’un bruit perturbateur aux données originales. Deux nouvelles approches sont développées dans le cadre de l’anonymisation par groupe, elles consistent à agréger les données à l’aide d’une technique de coclustering puis à utiliser le modèle produit, pour générer des enregistrements synthétiques, dans le cas de la première solution.
La deuxième proposition quant à elle, cherche à atteindre le formalisme du k-anonymat. Enfin, nous présentons DPCocGen un nouvel algorithme d’anonymisation respectueux de la confidentialité différentielle. Tout d’abord, un partitionnement sur les domaines est utilisé pour générer un histogramme multidimensionnel bruité, un co-clustering
multidimensionnel est ensuite effectué sur l’histogramme bruité résultant en un schéma de partitionnement. Enfin, le schéma obtenu est utilisé pour partitionner les données originales de manière différentiellement privée. Des individus synthétiques peuvent alors être tirés des partitions.
Mots-clés : protection de la vie privée, k-anonymat, confidentialité différentielle
**********
Abstract:
There is a strong economic and civic demand for the opening of individual data. However, the publication of such data poses a risk to the individuals represented in it. This
thesis focuses on the problem of anonymizing multidimensional data tables containing individual data for publishing purposes. In particular, two data anonymization approaches families will be focused on: the first aims to merge each individual into a group of individuals, the second is based on the addition of disruptive noise to the original data. Two new approaches are developed in the context of group anonymization. They aggregate the data using a co-clustering technique and then use the produced model, to generate synthetic records, in the case of the first solution. While the second proposal seeks to achieve the formalism of k-anonymity. Finally, we present a new anonymization algorithm “DPCocGen” that ensures differential privacy. First, a data-independent partitioning on the domains is used to generate a perturbed multidimensional histogram, a multidimensional co-clustering is then performed on the noisy histogram resulting in a partitioning scheme. Finally, the resulting schema is used to partition the original data in a differentially
private way. Synthetic individuals can then be drawn from the partitions.
Keywords: privacy preserving data publishing, k-anonymity, differential privacy
Marwa El Abri, doctorante au sein de l’équipe DUKe, soutiendra sa thèse intitulée « Apprentissage des Modèles Probabilistes Relationnels à partir des Bases de Données Graphe »
Mardi 2 octobre à partir de 9h30, à Polytech.
Jury : Philippe Leray (directeur de thèse), Nadia Essoussi (co directrice, ISG Tunis), Simon de Givry (rapporteur, INRA Toulouse), Nicolas Lachiche (U Strasbourg ICube), Nahla Ben Amor (ISG Tunis), Emmanuel Mazer (Inria Rhône Alpes)
Quentin Delmée, doctorant au sein de l’équipe SLP soutiendra sa thèse intitulée « Résolution Exacte de problèmes de localisation de services bi-objectif en variables mixtes »
vendredi 19 octobre 2018 à 10h00, dans l’amphi du bâtiment 34 sur le site de la Faculté des Sciences et Techniques
Jury : Xavier Gandibleux (directeur de thèse), Anthony Przybylski (co-encadrant), Laetitia Jourdan (Rapporteur, Université de Lille), Saïd Hanafi (Rapporteur, Université de Valenciennes et du Hainaut Cambrésis), André Rossi (examinateur, Université Paris Dauphine), Audrey Cerqueus (examinateur, Mines Saint-Etienne)
Résumé :
Dans ce travail, nous nous intéressons à la résolution exacte de problèmes de localisation de service en variables mixtes. Les problèmes de programmation linéaire bi-objectif en variables mixtes ont été très étudiés dans les dernières années, mais uniquement dans un contexte générique. De même, les problèmes de localisation de services bi-objectif n’ont été étudiés que dans un cas purement discret.
Nous considérons dans un premier temps le problème de localisation de services bi-objectif sans capacité. Afin de le résoudre, nous adaptons la méthode de pavage par boîtes proposée pour le cas discret. Les boîtes rectangulaires deviennent triangulaires dans le cas mixte. De plus, leur exploration est grandement facilitée, ce qui déplace la difficulté du problème dans l’énumération et le filtrage de ces boîtes. Différentes stratégies d’énumération sont proposées. Le problème de localisation de services bi-objectif avec capacité est ensuite considéré. Tout d’abord, une adaptation de la méthode de pavage par boîtes triangulaires est réalisée pour le cas avec capacité. Cependant, la nature du problème rend cette méthode beaucoup plus limitée. Nous considérons ensuite une méthode en deux phases dont la principale routine d’exploration repose sur une adaptation d’un algorithme de branch and bound initialement proposé par Beasley, dans le contexte bi-objectif.
Les résultats expérimentaux sur des instances aux caractéristiques variées attestent de la pertinence des méthodes que nous proposons.
Mots-clés : Optimisation bi-objectif, Problème de localisation de services, Programmation linéaire en variables mixtes, Branch and Bound
********
Abstract:
The purpose of this work is the exact solution of biobjective mixed-integer facility location problems. Biobjective mixed integer linear programming problem have been largely studied in recent years but only in the generic context. The same way, the study of biobjective facility location problems has been restrictedto the discrete case. We consider first the bi-objective uncapacitated facility location problem. To solve it, we adapt the box paving method proposed for the discrete case. Rectangular boxes become triangular. Moreover, their exploration becomes considerably easier. The difficulty of the problem is therefore translated to the enumeration and the filtering of these boxes. Different enumeration strategies are proposed. Next, we consider the bi-objective capacitated facility location problem. We first propose an adaptation of the triangular box paving method to the capacitated case. However, the structure of the problem highly limits the method. Thus, we consider a two phase method. The main exploration routine is based on the adaptation of a branch and bound algorithm proposed by Beasley that we adapt to the bi-objective context. Experimental results on various instances show the efficiency of the proposed methods.
Keywords: Bi-objective optimization, Facility Location Problems, Mixed Integer Linear Programming, Branch and Bound
