Le travail présenté dans ce mémoire étudie et propose des modèles de calcul parallèles de type cellulaire pour traiter différents problèmes d’optimisation NP-durs définis dans l’espace euclidien, et leur implantation sur des processeurs graphiques multi-fonction (Graphics Processing Unit; GPU). Le but est de pouvoir traiter des problèmes de grande taille tout en permettant des facteurs d’accélération substantiels à l’aide du parallélisme massif. Les champs d’application visés concernent les systèmes embarqués pour la stéréovision de même que les problèmes de transports définis dans le plan, tels que les problèmes de tournées de véhicules. La principale caractéristique du modèle cellulaire est qu’il est fondé sur une décomposition du plan en un nombre approprié de cellules, chacune comportant une part constante de la donnée, et chacune correspondant à une unité de calcul (processus). Ainsi, le nombre de processus parallèles et la taille mémoire nécessaire sont en relation linéaire avec la taille du problème d’optimisation, ce qui permet de traiter des instances de très grandes tailles.L’efficacité des modèles cellulaires proposés a été testée sur plateforme parallèle GPU sur quatre applications. La première application est un problème d’appariement d’images stéréo. Elle concerne la stéréovision couleur. L’entrée du problème est une paire d’images stéréo, et la sortie une carte de disparités représentant les profondeurs dans la scène 3D. Le but est de comparer des méthodes d’appariement local selon l’approche winner-takes-all et appliquées à des paires d’images CFA (color filter array). La deuxième application concerne la recherche d’améliorations de l’implantation GPU permettant de réaliser un calcul quasi temps-réel de l’appariement. Les troisième et quatrième applications ont trait à l’implantation cellulaire GPU des réseaux neuronaux de type carte auto-organisatrice dans le plan. La troisième application concerne la génération de maillages structurés appliquée aux cartes de disparité afin de produire des représentations compressées des surfaces 3D. Enfin, la quatrième application concerne le traitement d’instances de grandes tailles du problème du voyageur de commerce euclidien comportant jusqu’à 33708 villes.Pour chacune des applications, les implantations GPU permettent une accélération substantielle du calcul par rapport aux versions CPU, pour des tailles croissantes des problèmes et pour une qualité de résultat obtenue similaire ou supérieure. Le facteur d’accélération GPU par rapport à la version CPU est d’environ 20 fois plus vite pour la version GPU sur le traitement des images CFA, cependant que le temps de traitement GPU est d’environ de 0,2s pour une paire d’images de petites tailles de la base Middlebury. L’algorithme amélioré quasi temps-réel nécessite environ 0,017s pour traiter une paire d’images de petites tailles, ce qui correspond aux temps d’exécution parmi les plus rapides de la base Middlebury pour une qualité de résultat modérée. La génération de maillages structurés est évaluée sur la base Middlebury afin de déterminer les facteurs d’accélération et qualité de résultats obtenus. Le facteur d’accélération obtenu pour l’implantation parallèle des cartes auto-organisatrices appliquée au problème du voyageur de commerce et pour l’instance avec 33708 villes est de 30 pour la version parallèle. / The work presented in this PhD studies and proposes cellular computation parallel models able to address different types of NP-hard optimization problems defined in the Euclidean space, and their implementation on the Graphics Processing Unit (GPU) platform. The goal is to allow both dealing with large size problems and provide substantial acceleration factors by massive parallelism. The field of applications concerns vehicle embedded systems for stereovision as well as transportation problems in the plane, as vehicle routing problems. The main characteristic of the cellular model is that it decomposes the plane into an appropriate number of cellular units, each responsible of a constant part of the input data, and such that each cell corresponds to a single processing unit. Hence, the number of processing units and required memory are with linear increasing relationship to the optimization problem size, which makes the model able to deal with very large size problems.The effectiveness of the proposed cellular models has been tested on the GPU parallel platform on four applications. The first application is a stereo-matching problem. It concerns color stereovision. The problem input is a stereo image pair, and the output a disparity map that represents depths in the 3D scene. The goal is to implement and compare GPU/CPU winner-takes-all local dense stereo-matching methods dealing with CFA (color filter array) image pairs. The second application focuses on the possible GPU improvements able to reach near real-time stereo-matching computation. The third and fourth applications deal with a cellular GPU implementation of the self-organizing map neural network in the plane. The third application concerns structured mesh generation according to the disparity map to allow 3D surface compressed representation. Then, the fourth application is to address large size Euclidean traveling salesman problems (TSP) with up to 33708 cities.In all applications, GPU implementations allow substantial acceleration factors over CPU versions, as the problem size increases and for similar or higher quality results. The GPU speedup factor over CPU was of 20 times faster for the CFA image pairs, but GPU computation time is about 0.2s for a small image pair from Middlebury database. The near real-time stereovision algorithm takes about 0.017s for a small image pair, which is one of the fastest records in the Middlebury benchmark with moderate quality. The structured mesh generation is evaluated on Middlebury data set to gauge the GPU acceleration factor and quality obtained. The acceleration factor for the GPU parallel self-organizing map over the CPU version, on the largest TSP problem with 33708 cities, is of 30 times faster.

Le conflit entre la demande de services multimédia en multidiffusion à haut débit (MBMS) et les limites en ressources radio demandent une gestion efficace de l'allocation des ressources radio (RRM) dans les réseaux 3G UMTS. À l'opposé des travaux existant dans ce domaine, cette thèse se propose de résoudre le problème de RRM dans les MBMS par une approche d’optimisation combinatoire. Le travail commence par une modélisation formelle du problème cible, désigné comme Flexible Radio Resource Management Model (F2R2M). Une analyse de la complexité et du paysage de recherche est effectuée à partir de ce modèle. Tout d’abord on montre qu'en assouplissant les contraintes de code OVSF, le problème de RRM pour les MBMS peut s'apparenter à un problème de sac à dos à choix multiples (MCKP). Une telle constatation permet de calculer les limites théoriques de la solution en résolvant le MCKP similaire. En outre, l'analyse du paysage montre que les espaces de recherche sont accidentés et constellés d'optima locaux. Sur la base de cette analyse, des algorithmes métaheuristiques sont étudiés pour résoudre le problème. Nous montrons tout d'abord que un Greedy Local Search (GLS) et un recuit simulé (SA) peuvent trouver de meilleures solutions que les approches existantes implémentées dans le système UMTS, mais la multiplicité des optima locaux rend les algorithmes très instables. Un algorithme de recherche tabou (TS) incluant une recherche à voisinage variable (VNS) est aussi développé et comparé aux autres algorithmes (GLS et SA) et aux approches actuelles du système UMTS ; les résultats de la recherche tabou dépassent toutes les autres approches. Enfin les meilleures solutions trouvées par TS sont également comparées avec les solutions théoriques générées par le solveur MCKP. On constate que les meilleures solutions trouvées par TS sont égales ou très proches des solutions optimales théoriques. / The high throughputs supported by the multimedia multicast services (MBMS) and the limited radio resources result in strong requirement for efficient radio resource management (RRM) in UMTS 3G networks. This PhD thesis proposes to solve the MBMS RRM problem as a combinatorial optimization problem. The work starts with a formal modeling of the problem, named as the Flexible Radio Resource Management Model (F2R2M). An in-depth analysis of the problem complexity and the search landscape is done from the model. It is showed that, by relaxing the OVSF code constraints, the MBMS RRM problem can be approximated as a Multiple-Choice Knapsack Problem (MCKP). Such work allows us to compute the theoretical solution bounds by solving the approximated MCKP. Then the fitness landscape analysis shows that the search spaces are rough and reveal several local optimums. Based on the analysis, some metaheuristic algorithms are studied to solve the MBMS RRM problem. We first show that a Greedy Local Search (GLS) and a Simulated Annealing (SA) allow us to find better solutions than the existing approaches implemented in the UMTS system, however the results are instable due to the landscape roughness. Finally we have developed a Tabu Search (TS) mixed with a Variable Neighborhood Search (VNS) algorithm and we have compared it with GLS, SA and UMTS embedded algorithms. Not only the TS outperforms all the other approaches on several scenarios but also, by comparing it with the theoretical solution bounds generated by the MCKP solver, we observe that TS is equal or close to the theoretical optimal solutions.

Cette thèse porte sur la planification du personnel en accordant une attention particulière à l'aspect humain et aux facteurs ergonomiques dans le domaine de la production. Un certain nombre de modèles mathématiques sont présentés pour formuler les problèmes d'ordonnancement et de planification du personnel étudié. Concernant les modèles de planification, la productivité du système de fabrication et le bien-être des travailleurs sont ciblés. De cette manière, une méthode d'affectation des travailleurs est présentée pour réduire le temps de production et une méthode d'ordonnancement pour la rotation des tâches est présentée afin d’équilibrer la charge de travail des opérateurs. À cet effet, une analyse ergonomique est effectuée sur les postes de travail du système de production étudié. Cette analyse aboutit à l'évaluation des postes du travail suivant la convention dite des feux de circulation, c'est-à-dire que les postes sont classés dans les niveaux de charge faible, moyen et élevé qui sont représentés respectivement par les couleurs verte, jaune et rouge. Une approche mathématique est développée pour convertir ces résultats en valeurs numériques, car les paramètres quantitatifs sont plus applicables pour l'optimisation de la planification. Une programmation multi-objectifs est proposée pour optimiser les deux objectifs mentionnés du problème d'ordonnancement de tournée du personnel étudié. Les méthodes d'agrégation linéaire et de ε-contrainte sont appliquées pour résoudre ce modèle d'optimisation. En outre, cette thèse présente une nouvelle variante du problème d'affectation appelé problème d'affectation généralisée par séquence qui est défini pour la planification du personnel dans un système combiné constitué des postes de travail en série et en parallèle. Il est prouvé que ce problème d'optimisation combinatoire est NP-difficile et les méthodes exactes ne sont pas capables de résoudre les instances de grande taille. Ainsi, trois méthodes approchées composées de deux approches matheuristiques et une heuristique hybride sont développées pour résoudre ce problème. Les méthodes matheuristiques sont basées sur la décomposition de la formulation pour simplifier le modèle principal en deux ou plusieurs modèles plus petits. La troisième méthode est une heuristique gloutonne combinée à une recherche locale. En outre, dans la dernière étape de cette thèse, la planification des ressources humaines pour un système de soins à domicile est formulée mathématiquement. Selon la structure du système, une intégration des problèmes d'affectation et de tournées de véhicules est présentée. Enfin, une approche matheuristique en trois étapes est proposée pour résoudre ce problème d'optimisation combinatoire. / This thesis concerns the human resource planning by paying a special attention to the human aspect and ergonomic factors in the manufacturing domain. A number of mathematical models are presented to formulate the studied workforce scheduling and planning problems. In the planning models, the productivity of the manufacturing system and the well-being of the workers are targeted. In this way, a worker assignment approach is presented to reduce the production time and a job rotation scheduling approach is presented to balance the workloads on the operators. For this purpose, an ergonomic analysis is carried out on the jobs of the studied production system. This analysis results in the traffic light evaluation for the jobs, i.e., the jobs are categorized into the low, medium and high workload levels which are presented respectively by the green, yellow and red colors. A mathematical approach is developed to convert these outputs to the numerical values, because the quantitative parameters are more applicable for the optimization of the planning. A multi-objective programming is proposed to optimize two mentioned objectives of the studied workforce scheduling problem. Both linear aggregation and epsilon-constraint methods are applied to solve this optimization model. Furthermore, this thesis presents a novel variant of the assignment problem called sequencing generalized assignment problem which is defined for workforce scheduling in a combined system consisting of the jobs in series and in parallel. It is proved that this combinatorial optimization problem is NP-hard and the exact methods are not able to solve the large-scale instances. Hence, three approximate methods consisting of two matheuristic and a hybrid heuristic approaches are developed to solve it. The matheuristic methods are based on the decomposition of the formulation to break down and simplify the main model into two or more smaller models. The third method is a greedy heuristic combined with a local search. The efficiency of the three mentioned methods is evaluated by various instances of different sizes. Moreover, in the last step of this thesis, the human resource planning for a home healthcare system is formulated mathematically. According to the structure of the system, an integration of the worker assignment and vehicle routing problems is presented. Finally, a three-steps matheuristic approach is proposed to solve this combinatorial optimization problem.

Dans cette thèse, nous proposons des solutions parrallèles basées sur le systèmes actuel GPU (graphics processing unit) pour deux problèmes de minimisation de graphe Euclidien, à savoir le problème de forêt/arbre couvrant minimum Euclidien (EMSF / EMST) et le problème du voyageur commerce (TSP). Les solutions proposées résolvent également aussi le problème d'une paire bichromatique la plus proche (BCP), et suivent la technique de ``contrôle décentralisé, du parallélisme des données et des mémoires partagées par GPU".Nous proposons une technique de recherche dans le voisinage le plus proche de dimension K Euclidienne basée sur les approches classiques de NNS d’Elias qui divisent l’espace Euclidien en cellules congruentes et ne se chevauchant pas, où la taille des points de chaque cellule est délimitée. Nous proposons aussi une technique d'élagage pour obtenir le NNS à base de composants afin de trouver le point de sortie le plus proche de l'ensemble de points de requête de Q dans la complexité temporelle linéaire séquentielle lorsque les données sont uniformément réparties. Ces techniques sont utilisées conjointement avec deux GPU algorithmes proposés pour arbre traversement, à savoir la recherche en largeur bidirectionnelle GPU et la liste chaînée dynamique distribuée, afin d'adresser le BCP. Basé sur la solution BCP, un algorithme parallèle Divide and Conquer est implémenté pour construire EMSF et EMST totalement côté GPU. Le TSP est adressé avec différents algorithmes de recherche locaux parallèles 2-opt, dans lesquels nous proposons une méthodologie ``évaluation multiple K-opt, mouvements multiples K-opt" afin d’exécuter simultanément, sans interférence, des processus massifs 2-/3-opt mouvements qui se retrouvent globalement sur le même circuit TSP pour de nombreux bords. Cette méthodologie est expliquée en détail pour montrer comment nous obtenons un calcul haute performance à la fois du côté du GPU et CPU. Nous testons les solutions proposées et rapportons des résultats de comparaison expérimentale par rapport aux algorithmes de pointe. / In this thesis, we propose parallel solutions based on current graphics processing unit (GPU) system for two Euclidean graph minimization problems, namely the Euclidean minimum spanning forest/tree (EMSF/EMST) and the travelling salesman problem (TSP). The proposed solutions also solve the bichromatic closest pair (BCP) problem, and follow technique of ``decentralized control, data parallelism, GPU shared memories".We propose a Euclidean K-dimensional nearest neighbourhood search (NNS) technique based on classical Elias' NNS approaches that divide the Euclidean space into congruent and non-overlapping cells where size of points in each cell is bounded. We propose a pruning technique to obtain component-based NNS to find a query point set Q's closest outgoing point within sequential linear time complexity when the data is uniformly distributed. These techniques are used together with two proposed GPU tree traversal algorithms, namely the GPU two-direction Breadth-first search and distributed dynamic linked list, to address the BCP. Based on the BCP solution, a divide and conquer parallel algorithm is implemented for building EMSF and EMST totally on GPU side. The TSP is addressed with different parallel 2-opt local search algorithms, in which we propose a ``multiple K-opt evaluation, multiple K-opt moves" methodology in order to simultaneously execute, without interference, massive 2-/3-opt moves that are globally found on the same TSP tour for many edges. This methodology is explained in details to show how we obtain high performance computing both on GPU and CPU side. We test the proposed solutions and report experimental comparison results against the state-of-the-art algorithms.

No description available.

Les travaux présentés dans cette thèse portent sur l’imagerie computationnelle active et passive en micro-ondes. L’utilisation d’une cavité chaotique comme composants compressif est étudiée tant théoriquement (modèle mathématique, résolution algorithmique du problème inverse) et expérimentalement. L’idée sous-jacente est de remplacer un réseau d’antennes par une unique cavité réverbérante dont un réseau d’ouvertures sur la face avant permet de coder l’information spatiale d’une scène dans la réponse temporelle de la cavité. La réverbération des ondes électromagnétique à l’intérieur de la cavité fournit les degrés de liberté nécessaires à la reconstruction d’une image de la scène. Ainsi il est possible de réaliser en temps réel une image haute-résolution d’une scène à partir d’une unique réponse impulsionnelle. Les applications concernent la sécurité ou l’imagerie à travers les murs. Dans ce travail, la conception et la caractérisation d’une cavité chaotique ouverte sont effectuées. L’utilisation de ce dispositif pour réaliser en actif des images de cibles de diverses formes est démontrée. Le nombre de degrés de liberté est ensuite amélioré en modifiant les conditions aux limites grâce à l’ajout lampes fluorescentes. L’interaction des ondes avec ces éléments plasma permet de créer de nouvelles configurations de la cavité, améliorant ainsi la résolution des images. L’imagerie compressive est ensuite appliquée à la détection et localisation passive du rayonnement thermique naturel de sources de bruit, à partir de la corrélation des signaux reçus sur deux voies. Enfin, une méthode novatrice d’imagerie interférométrique de cibles est présentée. Elle est basée sur la reconstruction de la réponse impulsionnelle entre deux antennes à partir du bruit thermique micro-ondes émis par un réseau de néons. Ces travaux constituent une avancée vers les systèmes d’imagerie futurs. / The broad topic of the presented Ph.D focuses on active and passive microwave computational imaging. The use of a chaotic cavity as a compressive component is studied both theoretically (mathematical model, algorithmic resolution of the inverse problem) and experimentally. The underlying idea is to replace an array of antennas with a single reverberant cavity with an array of openings on the front panel that encodes the spatial information of a scene in the temporal response of the cavity. The reverberation of electromagnetic waves inside the cavity provides the degrees of freedom necessary to reconstruct an image of the scene. Thus it is possible to create a high-resolution image of a scene in real time from a single impulse response. Applications include security or imaging through walls. In this work, the design and characterization of an open chaotic cavity is performed. Using this device, active computational imaging is demonstrated to produce images of targets of various shapes. The number of degrees of freedom is further improved by changing the boundary conditions with the addition of commercial fluorescent lamps. The interaction of the waves with these plasma elements allows new cavity configurations to be created, thus improving image resolution. Compressive imaging is next applied to the passive detection and localization of natural thermal radiation from noise sources, based on the correlation of signals received over two channels. Finally, an innovative method of interferometric target imaging is presented. It is based on the reconstruction of the impulse response between two antennas from the microwave thermal noise emitted by a network of neon lamps. This work constitutes a step towards for future imaging systems.

La connaissance des structures internes de la Terre, à différentes échelles, présente des enjeux majeurs d'ordres économiques, humains, environnementaux et scientifiques. Diverses méthodes d'imagerie ont été développées en utilisant les informations contenues dans les ondes sismiques. La méthode d'inversion des formes d'ondes construit des images quantitative haute résolution des paramètres physiques du sous-sol, en exploitant le champ d'onde complet, sous la forme d'un problème d'optimisation. Dans ce travail de thèse, je présente l'application de l'inversion des formes d'ondes en domaine fréquentiel, pour imager les paramètres visco-élastiques dans des géometries à deux dimensions à grands offsets. Dans un premier temps les développements méthodologiques et algorithmiques sont présentés. La modélisation de la propagation des ondes P-SV en domaine fréquentiel, le problème direct du processus d'imagerie, est assurée par une méthode d'éléments finis Galerkin discontinus, assurant une grande flexibilité dans le choix des ordres d'interpolation et dans l'utilisation de maillages triangulaires non-structurés. Le problème inverse est résolu sous une forme linéarisée, afin de limiter le nombre de simulations directes, et utilise l'algorithme quasi-Newton L-BFGS permettant de tirer bénéfice de l'estimation "économique" du Hessien. Le processus global d'imagerie est implémenté sous la forme d'un algorithme massivement parallèle destiné aux calculateurs modernes à mémoire distribuée. Dans un deuxième temps, les algorithmes développés sont appliqués à des cas d'étude. Des applications sont menées dans des modèles synthétiques réalistes représentatifs d'environnements terrestres et marins. Ces études montrent les difficultés associées à la reconstruction des paramètres élastiques à partir de données mettant en jeu des phénomènes de propagations complexes (ondes converties, multiples, ondes de surfaces...). Des solutions sont proposées sous forme de processus hiérarchiques multi-échelles, afin de limiter les effets des non-linéarités du problème inverse et ainsi d'améliorer la convergence du processus vers le minimum global. Enfin, la sensibilité de différentes normes et critères de minimisation est analysée, à partir de données bruités issues de modèles synthétiques réalistes, ainsi que sous l'approximation acoustique pour un jeu de données réelles pétrolière. Ces tests montrent certaines limites du formalisme classique basé sur la norme L2 dans l'espace des données, tandis que la norme L1 apparaît comme alternative robuste pour l'inversion de données décimées en domaine fréquentiel.

L'amélioration constante de la résolution dynamique et temporelle des scanners et des méthodes de reconstruction en imagerie médicale, s'accompagne d'un besoin croissant en puissance de calcul. Les accélérations logicielles, algorithmiques et matérielles sont ainsi appelées à réduire le fossé technologique existant entre les systèmes d'acquisition et ceux de reconstruction.<br />Dans ce contexte, une architecture matérielle de rétroprojection 3D en Tomographie à Emission de Positons (TEP) est proposée. Afin de lever le verrou technologique constitué par la forte latence des mémoires externes de type SDRAM, la meilleure Adéquation Algorithme Architecture a été recherchée. Cette architecture a été implémentée sur un SoPC (System on Programmable Chip) et ses performances comparées à celles d'un PC, d'un serveur de calcul et d'une carte graphique. Associée à un module matériel de projection 3D, cette architecture permet de définir une paire matérielle de projection/rétroprojection et de constituer ainsi un système de reconstruction complet.

Des systèmes basés sur la chromatographie et la spectrométrie de masse sont utilisés pour analyser les échantillons biologiques comme l'urine ou le sang. Cette thèse propose une méthode, qui à partir des données, mesure la concentration de biomarqueurs. Dans la première partie du travail, nous élaborons un modèle décrivant chaque module de la chaîne d'analyse. Cependant, pour s'abstraire des fluctuations expérimentales, notre méthode doit évaluer certains paramètres instrument en plus des concentrations. La seconde partie consiste à traiter ce problème d'estimation non linéaire dans le cadre des approches statistiques bayésiennes. Cette démarche nous permet d'introduire de l'information supplémentaire, sous la forme de lois de probabilité, afin de régulariser le problème. La méthode est structurée autour d'un estimateur de la moyenne a posteriori. Sa mise en œuvre algorithmique utilise une boucle de Gibbs incluant un échantillonneur de Metropolis-Hastings.

En optique quantique, la reconstruction de l'état quantique (fonction de Wigner ou matrice de densité infini-dimensionnelle) d'un faisceau de lumière correspond en statistique à un problème inverse trés mal posé. Premièrement, nous proposons des estimateurs de la matrice de densité basés sur les fonctions \textit{pattern} et des estimateurs à noyau de la fonction de Wigner. Nous faisons l'hypothèse que la matrice de densité inconnue appartient à une classe non paramétrique définie en accord avec les exemples étudiés par les physiciens. Nous en déduisons pour la fonction de Wigner associée à cette matrice des propriétés de décroissance rapide et de régularité. Deuxièmement, nous estimons une fonctionnelle quadratique de la fonction de Wigner par une U-statistique d'ordre deux sur une classe plus large. Cette fonctionnelle peut être vue comme une indication sur la pureté de l'état quantique considéré. Nous en déduisons un estimateur adaptatif aux paramètres de régularité de la fonction de Wigner. La dernière partie de ce manuscrit est consacrée au problème de test d'adéquation à la matrice de densité. Cette procédure est construite à partir d'un estimateur de type projection sur les fonctions \textit{pattern}. Nous étudions les bornes supérieures de type minimax de toutes ces procédures. Les procédures d'estimation de la matrice de densité et de test d'adéquation à une matrice de densité sont implémentées et leurs performances numériques sont étudiées.