On considère le groupe de Heisenberg $\He_n=\R^{2n+1}$ avec la distance de Carnot-Carathéodory $d_c$ et la mesure de Lebegue $\Lg^{2n+1}$. Dans le premier chapitre, dans le cadre du problème du voyageur de commerce géométrique de $\Hei$, on construit une courbe de longueur finie qui ne vérifie pas le critère de Ferrari, Franchi et Pajot au sujet des ensembles contenus dans une courbe rectifiable. On montre aussi une inégalité sur le déterminant jacobien des applications de contraction sur un point qui suivent les géodésiques. Cette inégalité est essentiellement équivalente à la Propriété de Contraction de Mesure $MCP(0,2n+3)$. Grâce à cette proprété on répond positivement au Chapitre 2 à une question d'Ambrosio et Rigot à propos du transport de mesure dans $\He_n$ (travail en commun avec Figalli). Il s'avère en effet que les mesures traversées par une géodésique de l'espace de Wasserstein sont absolument continues dès qu'une extrémité de la géodésique l'est. Au Chapitre 3 on démontre que la Courbure-Dimension $CD(K,N)$ définie par transport de mesure n'est pas vérifiée pour $\He_n$ et que cela vaut quels que soient les paramètres $K\in\R$ et $N\in[1,+\infty]$. On discute aussi d'autres propriétés de courbures dans le cas du groupe de Heisenberg. Le Chapitre 4 est dédié à la correspondance entre l'équation de la chaleur sous-elliptique et le flot de gradient de l'entropie de Bolzmann dans l'espace de Wassertein.

La résolution jusqu'à l'optimalité de problèmes d'optimisation combinatoire NP-difficiles nécessite une mise en oeuvre de méthodes de plus en plus complexes qui consomment de plus en plus de puissance de calcul. L'objectif de notre travail est de paralléliser un algorithme de "Branch and Cut" pour résoudre jusqu'à l'optimalité des instances difficiles du voyageur de commerce. Dans la première partie de notre travail, nous présentons les composantes principales de l'algorithme du "Branch and Cut". Nous étudions ensuite le problème du voyageur de commerce par une approche polyédrale. Nous donnons enfin une description détaillée de notre implémentation de l'algorithme du "Branch and Cut". Dans la deuxième partie, Nous commençons par une brève présentation du parallélisme, et un état de l'art des études menées sur la parallélisation de l'algorithme du "Branch and Bound". Puis, nous proposons plusieurs modèles de parallélisations de l'algorithme du "Branch and Cut". Nous décrivons ensuite la stratégie de contrôle de la recherche arborescente qu'on a adopté, les mécanismes de minimisation des coûts liés aux différentes étapes de la communication entre les processeurs et les stratégies d'équilibrages. Nous terminons en donnant les résultats obtenus sur le IBM-SP1.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

L'optimisation des tournées de livraison est souvent modélisée par un problème de voyageur de commerce (Traveling Salesman Problem / TSP). Pour ce problème, il est fréquent d’avoir des contraintes additionnelles telles que, par exemple, des fenêtres horaires limitant les heures de livraison chez le client ou des pauses obligatoires pour les conducteurs des camions. Le temps est une dimension importante à prendre en compte pour respecter ces contraintes. Cependant, les durées des trajets ne sont généralement pas constantes mais varient en fonction des congestions, et cette variabilité doit être intégrée au moment de l’optimisation des tournées. Ainsi, le problème du voyageur de commerce dépendant du temps (Time Dependent TSP / TD-TSP) est la version étendue du TSP où le coût d'un arc dépend de l'heure à laquelle cet arc est emprunté. Dans cet thèse nous proposons un nouveau benchmark pour le TD-TSP basé sur des données réelles de trafic (fournies par la Métropole de Lyon) et nous montrons l'intérêt de prendre en compte la variabilité des durées dans ce problème. Nous étudions comment mieux modéliser les fonctions de durée de trajet dépendantes du temps. Nous introduisons et comparons différents modèles pour résoudre le TD-TSP avec la programmation par contraintes (Constraint Programming / CP). Un premier modèle est directement dérivé du modèle CP classique pour le TSP. Nous montrons que ce modèle ne permet pas de raisonner avec des relations de précédence indirectes, ce qui pénalise sa performance sur notre benchmark. Nous introduisons une nouvelle contrainte globale qui est capable d'exploiter des relations de précédence indirectes sur des données dépendantes du temps et nous introduisons un nouveau modèle CP basé sur notre nouvelle contrainte. Nous comparons expérimentalement les deux modèles sur notre benchmark, et nous montrons que notre nouvelle contrainte permet de résoudre le TD-TSP plus efficacement. / In the context of urban deliveries, the optimization of delivery tours is usually modeled as a Traveling Salesman Problem (TSP). Side constraints like time-windows constraining the delivery times at the client or breaks for the drivers are also common in this kind of problem and time is an important dimension to take into account to respect these constraints. With travel times' variability in big cities time also tends to have a greater influence in costs and therefore it should be included in the optimization of delivery routes. The Time-Dependent Traveling Salesman Problem (TDTSP) is the extended version of the Traveling Salesman Problem (TSP) where arc costs depend on the time when the arc is traveled. In this thesis we propose a set of benchmarks for the TDTSP based on real traffic data (obtained from the city of Lyon) and show the interest of handling time dependency in the problem. A study of how to better model time-dependent travel functions in general and specifically for our approach is performed. We introduce and compare different models to solve the TDTSP with Constraint Programming (CP). A first model is derived in a straightforward way from the classical CP model for the TSP. We show that this model is not able to reason on indirect precedence relations, so that it has poor performance on our benchmark. We introduce a new global constraint which is able to exploit indirect precedence relations on time-dependent data, and we introduce a second model which is based on our new constraint. We experimentally compare the two models on our benchmark.

Nous nous intéressons dans cette thèse aux possibilités d'hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l'objectif de résoudre des problèmes NPdifficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l'ordre des valeurs sur lesquelles brancher. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général est de tenir compte par une technique d'apprentissage de l'impact qu'ont eu les décisions de branchement dans les parties déjà explorées de l'arbre. Nous évaluons l'efficacité de la méthode proposée sur deux problèmes classiques : un problème d'optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, qui détermine par un algorithme de programmation dynamique la sous-séquence optimale d'un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d'être visités. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l'efficacité de l'opérateur que nous proposons en appliquant cette recherche à voisinage large sur deux problèmes, respectivement le Problème de l'Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d'Optimisation par Colonies de Fourmis. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu'il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l'aide de tests expérimentaux

Alors que le rat apprend à chercher de multiples sources de nourriture ou d'eau, des processus d'apprentissage de séquences spatiales et de rejeu ont lieu dans l'hippocampe et le cortex préfrontal.Des études récentes (De Jong et al. 2011; Carr, Jadhav, and Frank 2011) mettent en évidence que la navigation spatiale dans l'hippocampe de rat implique le rejeu de l'activation de cellules de lieu durant les étant de sommeil et d'éveil en générant des petites sous séquences contigues d'activation de cellules de lieu cohérentes entre elles. Ces fragments sont observés en particulier lors d'évènements sharp wave ripple (SPWR).Les phénomènes de rejeu lors du sommeil dans le contexte de la consolidation de la mémoire à long terme ont beaucoup attiré l'attention. Ici nous nous focalisons sur le rôle du rejeu pendant l'état d'éveil.Nous formulons l'hypothèse que ces fragments peuvent être utilisés par le cortex préfrontal pour réaliser une tâche d'apprentissage spatial comprenant plusieurs buts.Nous proposons de développer un modèle intégré d'hippocampe et de cortex préfrontal capable de générer des séquences d'activation de cellules de lieu.Le travail collaboratif proposé prolonge les travaux existants sur un modèle de cognition spatiale pour des tâches orientés but plus simples (Barrera and Weitzenfeld 2008; Barrera et al. 2015) avec un nouveau modèle basé sur le rejeu pour la formation de mémoire dans l'hippocampe et l'apprentissage et génération de séquences spatiales par le cortex préfrontal.En contraste avec les travaux existants d'apprentissage de séquence qui repose sur des règles d'apprentissage sophistiquées, nous proposons d'utiliser un paradigme calculatoire appelé calcul par réservoir (Dominey 1995) dans lequel des groupes importants de neurones artificiels dont la connectivité est fixe traitent dynamiquement l'information au travers de réverbérations. Ce modèle calculatoire par réservoir consolide les fragments de séquence d'activations de cellule de lieu en une plus grande séquence qui pourra être rappelée elle-même par des fragments de séquence.Le travail proposé est supposé contribuer à une nouvelle compréhension du rôle du phénomène de rejeu dans l'acquisition de la mémoire dans une tâche complexe liée à l'apprentissage de séquence.Cette compréhension opérationnelle sera mise à profit et testée dans l'architecture cognitive incarnée d'un robot mobile selon l'approche animat (Wilson 1991) [etc...] / As rats learn to search for multiple sources of food or water in a complex environment, processes of spatial sequence learning and recall in the hippocampus (HC) and prefrontal cortex (PFC) are taking place. Recent studies (De Jong et al. 2011; Carr, Jadhav, and Frank 2011) show that spatial navigation in the rat hippocampus involves the replay of place-cell firing during awake and sleep states generating small contiguous subsequences of spatially related place-cell activations that we will call "snippets". These "snippets" occur primarily during sharp-wave-ripple (SPWR) events. Much attention has been paid to replay during sleep in the context of long-term memory consolidation. Here we focus on the role of replay during the awake state, as the animal is learning across multiple trials.We hypothesize that these "snippets" can be used by the PFC to achieve multi-goal spatial sequence learning.We propose to develop an integrated model of HC and PFC that is able to form place-cell activation sequences based on snippet replay. The proposed collaborative research will extend existing spatial cognition model for simpler goal-oriented tasks (Barrera and Weitzenfeld 2008; Barrera et al. 2015) with a new replay-driven model for memory formation in the hippocampus and spatial sequence learning and recall in PFC.In contrast to existing work on sequence learning that relies heavily on sophisticated learning algorithms and synaptic modification rules, we propose to use an alternative computational framework known as reservoir computing (Dominey 1995) in which large pools of prewired neural elements process information dynamically through reverberations. This reservoir computational model will consolidate snippets into larger place-cell activation sequences that may be later recalled by subsets of the original sequences.The proposed work is expected to generate a new understanding of the role of replay in memory acquisition in complex tasks such as sequence learning. That operational understanding will be leveraged and tested on a an embodied-cognitive real-time framework of a robot, related to the animat paradigm (Wilson 1991) [etc...]

Dans cette thèse, nous nous intéressons à deux thèmes d'analyse géométrique. Le premier concerne le comportement asymptotique des fonctions harmoniques en relation avec la géométrie, sur des graphes et des variétés. Nous étudions des critères de convergence au bord des fonctions harmoniques, comme celui de la bornitude non-tangentielle, de la finitude de l'énergie ou encore de la densité de l'énergie. Nous nous plaçons pour cela dans différents cadres comme les graphes hyperboliques au sens de Gromov, les variétés hyperboliques au sens de Gromov, les graphes de Diestel-Leader ou encore dans un cadre abstrait pour obtenir des résultats pour les points du bord minimal de Martin. Les méthodes probabilistes utilisées exploitent le lien entre les fonctions harmoniques et les martingales. Le deuxième thème abordé dans cette thèse concerne l'étude des propriétés des ensembles rectifiables de dimension 1 dans le groupe de Heisenberg, en relation avec des opérateurs d'intégrales singulières. Nous étendons à ce contexte sous-riemannien une partie des résultats de la théorie des ensembles uniformément rectifiables de David et Semmes. Nous obtenons notamment un théorème géométrique du voyageur de commerce qui fournit une condition pour qu'un ensemble Ahlfors-régulier du premier groupe de Heisenberg soit contenu dans une courbe Ahlfors-régulière.

L'étude expérimentale d'algorithmes est un sujet crucial dans la conception de nouveaux algorithmes, puisque le contexte d'évaluation influence inévitablement la mesure de la qualité des algorithmes. Le sujet particulier qui nous intéresse dans l'étude expérimentale est la pertinence des instances choisies pour servir de base de test à l'expérimentation. Nous formalisons ce critère par la notion de "difficulté d'instance" qui dépend des performances pratiques de méthodes de résolution. Le coeur de la thèse porte sur un outil pour évaluer empiriquement la difficulté d'instance. L'approche proposée présente une méthode de benchmarking d'instances sur des jeux de test d'algorithmes. Nous illustrons cette méthode expérimentale pour évaluer des classes d'instances à travers plusieurs exemples d'applications sur le problème du voyageur de commerce. Nous présentons ensuite une approche pour générer des instances difficiles. Elle repose sur des opérations qui modifient les instances, mais qui permettent de retrouver facilement une solution optimale, d'une instance à l'autre. Nous étudions théoriquement et expérimentalement son impact sur les performances de méthodes de résolution.

Dans cette thèse, nous nous intéressons à deux thèmes d'analyse géométrique. Le premier concerne le comportement asymptotique des fonctions harmoniques en relation avec la géométrie, sur des graphes et des variétés. Nous étudions des critères de convergence au bord des fonctions harmoniques, comme celui de la bornitude non-tangentielle, de la finitude de l'énergie ou encore de la densité de l'énergie. Nous nous plaçons pour cela dans différents cadres comme les graphes hyperboliques au sens de Gromov, les variétés hyperboliques au sens de Gromov, les graphes de Diestel-Leader ou encore dans un cadre abstrait pour obtenir des résultats pour les points du bord minimal de Martin. Les méthodes probabilistes utilisées exploitent le lien entre les fonctions harmoniques et les martingales. Le deuxième thème abordé dans cette thèse concerne l'étude des propriétés des ensembles rectifiables de dimension 1 dans le groupe de Heisenberg, en relation avec des opérateurs d'intégrales singulières. Nous étendons à ce contexte sous-riemannien une partie des résultats de la théorie des ensembles uniformément rectifiables de David et Semmes. Nous obtenons notamment un théorème géométrique du voyageur de commerce qui fournit une condition pour qu'un ensemble Ahlfors-régulier du premier groupe de Heisenberg soit contenu dans une courbe Ahlfors-régulière. / In this thesis, we are interested in two topics of geometric analysis. The first one is concerned with the asymptotic behaviour of harmonic functions in connection with geometry on graphs and manifolds. We study criteria for convergence at boundary of harmonic functions such as non-tangential boundedness, finiteness of non-tangential energy or finiteness of the energy density. We deal with Gromov hyperbolic manifolds, Gromov hyperbolic graphs, Diestel-Leader graphs and with an abstract frame to obtain criteria at minimal Martin boundary points. The methods, coming from probability theory and metric geometry, use the relation between harmonic functions and martingales. The second topic concerns the rectifiability properties of 1-dimensional sets in the Heisenberg group in connection with the boundedness of singular integral operators. We extend to this sub-Riemannian setting parts of the theory of uniformly rectifiable sets due to David and Semmes. In particular, we obtain a geometric traveling salesman theorem which provides a condition for an Ahlfors regular set of the first Heisenberg group to be contained in an Ahlfors regular curve.

Plusieurs problèmes d'optimisation combinatoire sont dits NP-difficiles et ne peuvent être résolus de façon optimale par des algorithmes exacts. Les métaheuristiques ont prouvé qu'elles pouvaient être efficaces pour résoudre un grand nombre de ces problèmes en leur trouvant des solutions approchées en un temps raisonnable. Cependant, face à des instances de grande taille, elles ont besoin d'un temps de calcul et d'une quantité d'espace mémoire considérables pour être performantes dans l'exploration de l'espace de recherche. Par conséquent, l'intérêt voué à leur déploiement sur des architectures de calcul haute performance a augmenté durant ces dernières années. Les approches de parallélisation existantes suivent généralement les paradigmes de passage de messages ou de mémoire partagée qui conviennent aux architectures traditionnelles à base de microprocesseurs, aussi appelés CPU (Central Processing Unit).Cependant, la recherche évolue très rapidement dans le domaine du parallélisme et de nouvelles architectures émergent, notamment les accélérateurs matériels qui permettent de décharger le CPU de certaines de ses tâches. Parmi ceux-ci, les processeurs graphiques ou GPU (Graphics Processing Units) présentent une architecture massivement parallèle possédant un grand potentiel mais aussi de nouvelles difficultés d'algorithmique et de programmation. En effet, les modèles de parallélisation de métaheuristiques existants sont généralement inadaptés aux environnements de calcul de type GPU. Certains travaux ont d'ailleurs abordé ce sujet sans toutefois y apporter une vision globale et fondamentale.L'objectif général de cette thèse est de proposer un cadre de référence permettant l'implémentation efficace des métaheuristiques sur des architectures parallèles basées sur les GPU. Elle débute par un état de l'art décrivant les travaux existants sur la parallélisation GPU des métaheuristiques et les classifications générales des métaheuristiques parallèles. Une taxonomie originale est ensuite proposée afin de classifier les implémentations recensées et de formaliser les stratégies de parallélisation sur GPU dans un cadre méthodologique cohérent. Cette thèse vise également à valider cette taxonomie en exploitant ses principales composantes pour proposer des stratégies de parallélisation originales spécifiquement adaptées aux architectures GPU. Plusieurs implémentations performantes basées sur les métaheuristiques d'Optimisation par Colonie de Fourmis et de Recherche Locale Itérée sont ainsi proposées pour la résolution du problème du Voyageur de Commerce. Une étude expérimentale structurée et minutieuse est réalisée afin d'évaluer et de comparer la performance des approches autant au niveau de la qualité des solutions trouvées que de la réduction du temps de calcul. / Several combinatorial optimization problems are NP-hard and can only be solved optimally by exact algorithms for small instances. Metaheuristics have proved to be effective in solving many of these problems by finding approximate solutions in a reasonable time. However, dealing with large instances, they may require considerable computation time and amount of memory space to be efficient in the exploration of the search space. Therefore, the interest devoted to their deployment on high performance computing architectures has increased over the past years. Existing parallelization approaches generally follow the message-passing and shared-memory computing paradigms which are suitable for traditional architectures based on microprocessors, also called CPU (Central Processing Unit). However, research in the field of parallel computing is rapidly evolving and new architectures emerge, including hardware accelerators which offloads the CPU of some of its tasks. Among them, graphics processors or GPUs (Graphics Processing Units) have a massively parallel architecture with great potential but also imply new algorithmic and programming challenges. In fact, existing parallelization models of metaheuristics are generally unsuited to computing environments like GPUs. Few works have tackled this subject without providing a comprehensive and fundamental view of it.The general purpose of this thesis is to propose a framework for the effective implementation of metaheuristics on parallel architectures based on GPUs. It begins with a state of the art describing existing works on GPU parallelization of metaheuristics and general classifications of parallel metaheuristics. An original taxonomy is then designed to classify identified implementations and to formalize GPU parallelization strategies in a coherent methodological framework. This thesis also aims to validate this taxonomy by exploiting its main components to propose original parallelization strategies specifically tailored to GPU architectures. Several effective implementations based on Ant Colony Optimization and Iterated Local Search metaheuristics are thus proposed for solving the Travelling Salesman Problem. A structured and thorough experimental study is conducted to evaluate and compare the performance of approaches on criteria related to solution quality and computing time reduction.