Th. 3e cycle--Méthodes d'approximation et algorithmes en analyse et théorie des nombres--Besançon, 1979. N°: 311.

Thèse doctorat : Informatique : Villeurbanne, INSA : 2003. / Titre provenant de l'écran-titre. Bibliogr. p. 140-148.

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.

Étant donnes un graphe g=(v,e) et une fonction cout définie sur les arêtes de ce graphe, cette thèse étudie le problème du voyageur de commerce relaxe qui consiste a trouver une tournée sur G, de longueur minimum, telle que chaque sommet soit visite au moins au fois

.

Ce travail de thèse comporte deux composantes, l'une théorique sur l'enveloppe convexe des cycles hamiltoniens, aussi appelée polytope du Voyageur de Commerce, et une autre plus numérique sur l'amélioration de la résolution exacte par la méthode "Branch & Cut'' du problème du Voyageur de Commerce. L'apport théorique consiste en la démonstration qu'une classe d'inéquations, les contraintes de domino, induisent des facettes du polytope du Voyageur de Commerce. L'aspect numérique aborde la séparation hors paradigme de classe en proposant la génération de coupes à partir de la contraction d'un grand graphe en un plus petit à l'aide de la représentation en cactus des coupes minimum. Enfin diverses pistes ont été étudiées pour rendre l'étape de branchement plus robuste.

Le probleme du voyageur de commerce, note TSP, consiste a trouver un parcours de longueur minimum que doit emprunter un voyageur pour visiter une et une seule fois chaque ville s'il demarre de la ville de son domicile et y revient en fin de parcours. Dans cette these, nous etudions une generalisation de ce probleme. Si on regroupe les villes par pays, on s'interesse a un parcours de longueur minimum qui visite une et une seule ville de chaque pays. Cette generalisation est ainsi appelee probleme du voyageur de commerce international, note ITSP. Le ITSP est un probleme NP-difficile. Dans une premiere partie, nous decrivons des heuristiques pour le ITSP et nous evaluons numeriquement une nouvelle heuristique pour le TSP basee sur des notions introduites par Glover. Nous decrivons une reduction polynomiale du ITSP au TSP et nous donnons une nouvelle formulation du ITSP en un programme lineaire en nombres entiers. La deuxieme partie est reservee a l'approche de resolution polyedrale. Nous definissons la relaxation graphique du ITSP et nous donnons des resultats sur la dimension et la structure faciale du polyedre associe. Nous etudions la relation polyedrale qui existe entre le ITSP et sa relaxation graphique et nous introduisons plusieurs classes de facettes du polytope du ITSP. L'etude polyedrale du ITSP nous a permis de developper un algorithme de branchement et de coupe pour sa resolution. Nous presentons des heuristiques et des algorithmes exacts pour la separation de certaines classes de facettes et nous donnons les principales modifications qu'il faut apporter a un algorithme de branchement et de coupe pour le TSP afin d'obtenir un tel algoritme pour le ITSP. Nous finissons cette etude en donnant quelques resultats numeriques et une anlyse de l'implantation que nous avons realisee.

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.

Reproduction de : Thèse de doctorat : Automatique et informatique industrielle : Villeneuve d'Ascq, Ecole centrale de Lille : 2006. / Titre provenant de la page de titre du document numérisé. Bibliogr. p. 183-194. Index.

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