Dans cette thèse, nous nous intéressons aux problèmes d'optimisation dans les réseaux de télécommunication. Un premier objectif consiste à identifier les problèmes spécifiques aux réseaux optiques et satellitaires, et à présenter des contributions pour l'optimisation des ressources de ces réseaux. Le second objectif est de présenter une contribution logicielle pour la conception et l'optimisation de réseaux.<br /><br />La première partie débute par la présentation des réseaux optiques WDM. Nous abordons ensuite les modèles pour les réseaux optiques et satellitaires et proposons des méthodes algorithmiques nouvelles pour optimiser l'allocation des ressources de ces réseaux. Nous traitons ainsi le problème du routage, du groupage et de la protection des réseaux WDM successivement dans trois chapitres puis nous nous intéressons à un algorithme dédié à l'allocation de fréquences dans les réseaux satellitaires. Enfin, pour chaque problème, nous présentons des résultats expérimentaux sur des instances de réseaux réels.<br /><br />La deuxième partie de cette thèse présente les développements logiciels qui ont été entrepris. Le premier chapitre présente le logiciel Porto dédié à la résolution de problèmes de routage, groupage et protection dans des réseaux optiques utilisant trois niveaux de brassage. Dans un second chapitre nous présentons le logiciel Mascopt, une bibliothèque d'optimisation pour le domaine des graphes et des réseaux qui a servi notamment à réaliser les expérimentations présentées dans la première partie.

Les travaux présentés dans cette thèse concernent l'ordonnancement<br />pour les plates-formes hétérogènes à grande échelle. Nous nous<br />intéressons principalement aux opérations de communications<br />collectives comme la diffusion de données, la distribution de données<br />ou la réduction. Nous étudions ces problèmes dans le cadre de leur<br />régime permanent, en optimisant le débit d'une série d'opérations de<br />communications, en vue d'obtenir un ordonnancement asymptotiquement<br />optimal du point de vue du temps d'exécution total. Après avoir<br />présenté un cadre général d'étude qui nous permet de connaître la<br />complexité du problème pour chaque primitive, nous développons, pour<br />le modèle de communication un-port bidirectionnel, une méthode de<br />résolution pratique fondée sur la résolution d'un programme linéaire<br />en rationnels. Cette étude du régime permanent est illustrée par des<br />expérimentations sur Grid5000 et se prolonge vers l'ordonnancement<br />d'applications multiples sur des grilles de calcul.

Les travaux de cette thèse concernent la conception et l'optimisation de lignes de transfert reconfigurables. L'objectif principal est de concevoir une ligne d'usinage à moindre coût tout en respectant les contraintes techniques, technologiques et économiques du problème. Le problème d'optimisation correspondant est un problème d'équilibrage de lignes d'usinage sujet à des contraintes spécifiques. Il consiste à affecter les opérations aux stations de travail en minimisant les coûts d'installation. En plus des contraintes habituelles de ce type de problème, à savoir, les contraintes de précédence, d'inclusion et d'exclusion, nous avons dû considérer des contraintes d'accessibilité. De plus, la spécificité principale des lignes reconfigurables par rapport aux lignes de transfert dédiées, vient de la réalisation en série des opérations. Celle-ci rend souvent nécessaire la mise en place de stations équipées de plusieurs centres d'usinage travaillant en parallèle pour obtenir les volumes de production souhaités. Enfin, l'utilisation d'une tête d'usinage mono-broche induit la prise en compte de temps inter-opératoire de déplacements et de changement d'outils qui dépendent de la séquence d'opérations. Dans un premier temps, nous avons proposé une modélisation mathématique du problème à l'aide d'un programme linéaire en nombres mixtes. Nous avons aussi développé des méthodes de calcul de bornes inférieures ainsi qu'une procédure de prétraitement. Cependant, les contraintes additionnelles rendent la résolution du problème d'équilibrage plus difficile que dans le cas des lignes dédiées, et l'approche proposée ne permet généralement pas de résoudre des instances de taille industrielle. Pour répondre à ce besoin, nous avons donc développé plusieurs méthodes de résolution approchées du problème en nous inspirant de métaheuristiques efficaces sur des problèmes d'optimisation combinatoire.

Le problème d'alignement de graphes, qui joue un rôle central dans différents domaines de la reconnaissance de formes, est l'un des plus grands défis dans le traitement de graphes. Nous proposons une méthode approximative pour l'alignement de graphes étiquetés et pondérés, basée sur la programmation convexe concave. Une application importante du problème d'alignement de graphes est l'alignement de réseaux d'interactions de protéines, qui joue un rôle central pour la recherche de voies de signalisation conservées dans l'évolution, de complexes protéiques conservés entre les espèces, et pour l'identification d'orthologues fonctionnels. Nous reformulons le problème d'alignement de réseaux d'interactions comme un problème d'alignement de graphes, et étudions comment les algorithmes existants d'alignement de graphes peuvent être utilisés pour le résoudre. Dans la formulation classique de problème d'alignement de graphes, seules les correspondances bijectives entre les noeuds de deux graphes sont considérées. Dans beaucoup d'applications, cependant, il est plus intéressant de considérer les correspondances entre des ensembles de nœuds. Nous proposons une nouvelle formulation de ce problème comme un problème d'optimisation discret, ainsi qu'un algorithme approximatif basé sur une relaxation continue. Nous présentons également deux résultats indépendants dans les domaines de la traduction automatique statistique et de la bio-informatique. Nous montrons d'une part comment le problème de la traduction statistique basé sur les phrases peut être reformulé comme un problème du voyageur de commerce. Nous proposons d'autre part une nouvelle mesure de similarité entre les sites de fixation de protéines, basée sur la comparaison 3D de nuages atomiques.

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

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. Mots clés : Optimisation Combinatoire, Polyèdres, Algorithme à Plans Coupants, Graphes

Les travaux de recherche effectués dans le cadre de cette thèse concernent essentiellement la conception en avant-projet de systèmes d'usinage dédiés à la production en grande série. Lors de cette phase de conception, l'objectif principal est de trouver, pour une pièce donnée, une configuration du système d'usinage qui satisfaisait, à coût minimal, les contraintes technologiques, techniques et économiques existantes. Plusieurs problèmes combinatoires posés par cet objectif sont étudiés dans la thèse. Plus concrètement, nous nous sommes intéressés aux problèmes d'optimisation de la configuration des trois types de systèmes d'usinage suivants : machines de transfert, machines à table mobile et machines à table circulaire pivotante. Pour chacun de ces systèmes, nous avons proposé, dans un premier temps, différents modèles mathématiques. Dans un deuxième temps, nous avons développé de nombreux outils d'optimisation dédiés à leur résolution, tels que des algorithmes de calcul des bornes inférieures, des procédures de pré-traitement, des algorithmes de résolution exacte et approchée, et des approches mixtes utilisant plusieurs de ces algorithmes. Ces travaux ont permis de concevoir un prototype de logiciel destiné à supporter les différentes étapes de conception en avant projet d'un système d'usinage. Ce logiciel a été testé avec succès sur plusieurs cas industriels.

Ce manuscrit est décomposé en un chapitre introductif et deux parties principales.<br /><br />Le chapitre 1, pose le contexte du travail. Pour cela les principales définitions liées à l'optimisation combinatoire multi-objectif sont présentées. Puis, les problématiques spécifiques à ce domaine sont exposées et étudiées. Parmi ces problématiques nous parlerons en particulier de la structure de l'ensemble des solutions de compromis (solutions Pareto), du choix des méthodes de résolution et de l'analyse de performances en multi-objectif. Ce chapitre permettra de cerner ce qui est étudié dans le manuscrit et ce qui ne l'est pas.<br /><br />La première partie (chapitres 2 et 3) traite de la coopération de méthodes en vue d'améliorer les résultats des méthodes d'optimisation combinatoire multi-objectif. Au cours de cette partie, un problème d'ordonnancement - problème de flowshop de permutation bi-objectif - est utilisé à titre d'exemple. Nous commençons donc le chapitre 2 par la présentation de ce problème. Puis, le chapitre s'attarde sur les méthodes exactes pour l'optimisation multi-objectif. Ces méthodes n'étant pas nombreuses, une revue de la littérature est réalisée. Inspirée de cette étude, un nouveau schéma de méthode exacte - PPM - est proposé.<br /> Le chapitre 3 s'intéresse à la coopération entre méthodes. Pour cela, la première partie du chapitre concerne l'utilisation des métaheuristiques en multi-objectif. Ainsi, après avoir présenté nos travaux concernant le développement d'un algorithme génétique pour le flowshop bi-objectif, une présentation rapide des méthodes les plus connues est réalisée. Puis, la deuxième partie discute des possibilités de coopération entre les différentes méthodes et présente les résultats obtenus.<br /><br />La deuxième partie (chapitres 4, 5 et 6) s'intéresse à un tout autre domaine d'application. Il s'agit de l'extraction de connaissances. En effet, de nombreux problèmes d'extraction de connaissances peuvent être modélisés, entièrement ou en partie, en des problèmes d'optimisation combinatoire. C'est ce que nous présentons dans le chapitre 4. Dans ce chapitre, une partie est consacrée à l'apport du multi-objectif pour ce type de problèmes. Puis, une étude plus approfondie porte sur la problématique de recherche de règles d'association. Pour ce problème, nous exposons la modélisation multi-objectif proposée ainsi que les méthodes de résolution développées.<br /> Le chapitre 5 présente deux approches coopératives : une approche coopérative parallèle mettant en jeux plusieurs métaheuristiques et une coopération avec une méthode exacte.<br /> Finalement, le chapitre 6 donne des indications sur le contexte applicatif utilisé, à savoir l'étude de données issues de la bio-informatique.<br />Au cours du mémoire, chaque chapitre se termine par un certain nombre de perspectives. Le dernier chapitre, conclusions et perspectives, fait une synthèse des principaux apports des travaux présentés dans le manuscrit ainsi que des perspectives annoncées.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3514. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. p. [149]-160.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3467. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. 9 p.