É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

.

Cette thèse aborde le problème de la résolution des problèmes combinatoires à l'aide d'algorithmes génétiques. Ce type d'algorithme présente en effet nombres d'avantages. Cependant, ils sont généralement relativement lents. Cette thèse est donc centrée sur les algorithmes hybrides, c'est-à-dire des algorithmes construits à l'aide de plusieurs méthodes différentes. Dans notre cas, nous étudions les algorithmes qui réunissent algorithmes génétiques et heuristiques. Il existe deux méthodes pour générer de tels algorithmes qui sont la représentation directe et la représentation indirecte. Ces deux méthodes sont étudiés au travers de trois problèmes distincts : l'ordonnancement statique de programmes parallèles, le placement de composants électroniques et la planification de réseaux cellulaires. Pour chacun des trois problèmes, les algorithmes hybrides ont montrés leur efficacité. Pour le problème de la planification de réseaux cellulaires, une nouvelle modélisation a été faite. Cette modélisation permet d'effectuer en même temps le placement des émetteurs et l'allocation de fréquences.

Le travail présenté dans cette thèse traite de l'extraction de connaissances à l'aide de métaheuristiques et de ses applications à des problématiques en génomique. Dans un premier temps, nous donnons un état de l'art des métaheuristiques utilisées pour l'extraction de connaissances et plus particulièrement de l'utilisation des algorithmes génétiques en orientant notre présentation sur trois aspects fondamentaux des métaheuristiques : la représentation d'une solution, la fonction d'évaluation et le choix des opérateurs. Nous présentons ensuite deux problématiques issues d'une collaboration avec l'Institut de Biologie de Lille autour de la recherche de facteurs génétiques de prédisposition à certaines maladies multifactorielles (diabète de type II, obésité). Nous proposons une modélisation de ces problèmes en problèmes d'extraction de connaissances. Nous traitons ensuite les différentes taches d'extraction de connaissances identifiées comme des problèmes d'optimisation et proposons un schéma d'algorithme génétique possédant des mécanismes avancés d'intensification et de diversification pour les résoudre. Les apports de ces mécanismes sont testés modulairement afin de montrer leurs performances. Nous intégrons également des connaissances du domaine biologique afin de répondre aux problématiques posées. Cette intégration s'effectue aussi bien au niveau des fonctions d'évaluation proposées qu'au niveau de certains mécanismes utilisés. Enfin, différents modèles de parallélisme sont utilisés.

La demande croissante de puissance de calcul est telle que des ordinateurs de plus en plus performants sont fabriques. Afin que ces machines puissent etre facilement exploitees, les lacunes actuelles en terme d'environnements de programmation doivent etre comblees. Le but a atteindre est de trouver un compromis entre recherche de performances et portabilite. Cette these s'interesse plus particulierement au placement statique de graphes de taches sur architectures paralleles a memoire distribuee. Ce travail s'inscrit dans le cadre du projet INRIA-IMAG APACHE et du projet europeen SEPP-COPERNICUS (Software Engineering for Parallel Processing). Le graphe de taches sans precedence est le modele de representation de programmes paralleles utilise dans cette these. Un tour d'horizon des solutions apportees dans la litterature au probleme de l'ordonnancement et du placement est fourni. La possibilite d'utilisation des algorithmes de placement sur des graphes de precedence, apres une phase de regroupement, est soulignee. Une solution originale est proposee, cette solution est interfacee avec un environnement de programmation complet. Trois types d'algorithmes (gloutons, iteratifs et exacts) ont ete concus et implementes. Parmi ceux-ci, on retrouve plus particulierement un recuit simule et une recherche tabu. Ces algorithmes optimisent differentes fonctions objectives (des plus simples et universelles aux plus complexes et ciblees). Les differents parametres caracterisant le graphe de taches peuvent etre affines suite a un releve de traces. Des outils de prise de traces permettent de valider les differentes fonctions de cout et les differents algorithmes d'optimisation. Un jeu de tests est defini et utilise. Les tests sont effectue sur le Meganode (machine a 128 transputers), en utilisant comme routeur VCR de l'universite de Southampton, les outils de generation de graphes synthetiques ANDES du projet ALPES (developpe par l'equipe d'evaluation de performances du LGI-IMAG) et l'algorithme de regroupement DSC (Dominant Sequence Clustering) de PYRROS (developpe par Tao Yang et Apostolos Gerasoulis). Mapping task graphs on distributed memory parallel computers

Nous proposons des méthodes et des outils pour l'aide à la conception stratégique de réseaux de transports publics en milieu urbain. Un état de l'art des problèmes de synthèse de réseaux est suivi par la définition du problème de synthèse de réseaux de mobilité avec demande élastique (dépendante de la qualité de service) . Nous déclinons différentes modélisations et des extensions étudiées de manière exacte sur de modestes instances. Les métaheuristiques GRASP et Tabou permettent d'obtenir de bonnes solutions sur des instances plus grandes. Nous utilisons pour cela la "géodésique", une description particulière de circuit. La résolution est accélérée en introduisant une fonction objectif auxiliaire. Enfin, nous utilisons une méthode inspirée du schéma de Benders. En annexe, nous formalisons des schémas de conception de composants logiciels flexibles et performants avec la programmation générique. Nous présentons aussi le couplage par enrichissement, entre optimisation et simulation.

Cette thèse d'Habilitation à Diriger des Recherches revient sur une dizaine d'années de contributions théoriques et pratiques à l'optimisation combinatoire, contributions dont le domaine d'application privilégié est l'optimisation des systèmes de télécommunications (principalement les autocommutateurs pour la téléphonie cellulaire) et informatiques (en particulier les architectures de processeur parallèles, dites multi-cœurs). Ces travaux se caractérisent également par la résolution bout-en-bout de nombreux cas d'applications industriels concrets et difficiles, de la modélisation mathématique initiale jusqu'à la mise en œuvre d'algorithmes de résolution opérationnels en passant par les développements théoriques nécessaires à leurs fondements.

Ce travail de thèse de doctorat traite de l'étude d'un problème d'ordonnancement NP-difficile au sens fort à contraintes de ressource : le problème de la programmation des déplacements de processus. Ce problème, issu de l'industrie des télécommunications, est lié à l'opérabilité de certains systèmes temps réel répartis à haute disponibilité tels le BSCe3, un autocommutateur pour la téléphonie cellulaire commercialisé par Nortel.<br />En quelques mots, ce problème consiste, étant donnée une répartition arbitraire admissible de processus sur les processeurs d'un système réparti, à trouver une séquence d'opérations (migrations de processus sans effet sur le service ou arrêts temporaires) de moindre impact par le biais de laquelle une autre répartition arbitraire, et fixée à l'avance, peut être obtenue. La principale contrainte réside dans le fait que la capacité des processeurs du système ne doit pas être dépassée durant la reconfiguration.<br />Nous avons abordé ce problème d'ordonnancement sous différents angles. Tout d'abord, nous avons établi son caractère NP-difficile au sens fort et exhibé quelques cas particuliers polynomiaux. Puis, sur le plan de la résolution exacte dans le cas général, nous avons conçu deux algorithmes de recherche arborescente : le premier trouve ses fondements dans l'étude de la structure combinatoire du problème, le second dans des considérations polyédrales. De nombreux résultats expérimentaux illustrent la pertinence pratique de ces deux algorithmes. Enfin, en raison des contraintes imposées par le caractère temps réel de notre application industrielle, nous avons mis au point un algorithme efficace de résolution approchée basé sur la métaheuristique du recuit simulé et, en capitalisant sur nos travaux en résolution exacte, empiriquement vérifié sa capacité pratique à produire des solutions acceptables, en un sens bien défini.

Cette synthèse de travaux de recherche concerne l'algorithmique dans les graphes et l'utilisation de la pro- grammation linéaire et semidéfinie positive (SDP) dans le cadre de la résolution exacte ou approchée de plusieurs problèmes fondamentaux de l'Optimisation Combinatoire. L'approche semidéfinie, qui conduit à des relaxations convexes mais non-linéaires, a permis d'obtenir de remarquables résultats théoriques en approximation et devient à présent utilisable en pratique (tout comme la programmation linéaire qui en est un cas particulier). Nos travaux comportent une forte composante algorithmique et des études de complexité de plusieurs problèmes d'optimisation dans les graphes. Nous considérons tout d'abord le problème de la recherche d'un sous-graphe dense de taille fixée pour lequel nous présentons un algorithme polynomial avec ga- ranties de performances fondé sur la programmation linéaire et quadratique. Puis, nous étudions les problèmes de multiflots entiers et de multicoupes pour lesquels nous avons identifié de nombreux cas po- lynomiaux dans des graphes particuliers importants en pratique : arborescences, grilles, anneaux. D'une part, les solutions fractionnaires fournies par certaines relaxations linéaires de ces problèmes sont le point de départ d'algorithmes de résolution efficaces. D'autre part, les propriétés des programmes linéaires uti- lisés nous permettent également d'élaborer des algorithmes purement combinatoires et de démontrer leur validité (matrices totalement unimodulaires, théorème des écarts complémentaires). Nous proposons également des approches systématiques pour élaborer des relaxations semidéfinies pour les programmes quadratiques, modèles de très nombreux problèmes combinatoires et continus. Plus précisément, nous étudions les liens entre relaxations semidéfinies et des relaxations lagrangiennes partielles de programmes quadratiques contenant des contraintes linéaires. En particulier, les fonctions quadratiques constantes sur une variété affine sont entièrement caractérisées. Ceci permet de facilement comparer les différentes familles de contraintes redondantes proposées dans la littérature dans l'approche semidéfinie dans le cadre unifié de l'approche lagrangienne. Puis, nous présentons un algorithme pour élaborer des relaxations semidéfinies à partir de relaxations linéaires existantes. L'objectif est de pro- fiter des résultats théoriques et expérimentaux obtenus dans l'approche linéaire. Nous avons développé un logiciel (SDP_S) grâce à ces résultats. Il permet de formuler automatiquement et facilement des relaxations semidéfinies pour tout problème pouvant être formulé comme un programme quadratique en variables bivalentes. Notre méthode peut se généraliser à certains programmes à variables mixtes. Enfin, nous appliquons les méthodes décrites précédemment à une série de problèmes combinatoires classiques. Nos expérimentations montrent que l'approche semidéfinie est à présent pertinente dans la pra- tique sous certaines conditions. Premièrement, nous présentons des méthodes de séparation/évaluation efficaces fondées sur la SDP pour la résolution exacte des problèmes max 2sat et Vertex-Cover. Deuxièmement, nous proposons plusieurs bornes par SDP de grande qualité pour des problèmes particu- lièrement difficiles à résoudre par les approches linéaires : k-cluster, CMAP (un problème de placement de tâches avec contraintes de ressources), et le problème de l'affectation quadratique (QAP). Pour ce dernier nous présentons également un algorithme de coupes performant fondé sur la programmation semidéfinie. Afin d'obtenir des algorithmes efficaces en pratique, nous mettons en oeuvre non seulement nos méthodes d'élaboration de relaxations SDP, mais également des techniques algorithmiques issues de l'approximation polynomiale, ainsi que des outils spécifiques de résolution numérique des programmes semidéfinis.

L'ouverture des marchés de l'énergie et la volonté grandissante de protéger l'environnement va conduire au développement massif de la production décentralisée. Les réseaux de transport, déjà saturés, devront être soutenus par les réseaux de distribution auxquels ces nouvelles sources seront connectées. Néanmoins, l'introduction massive de productions décentralisées pourrait modifier le fonctionnement des réseaux de distribution électrique. Cette thèse illustre un meilleur moyen d'accueillir ces productions par l'introduction de nouveaux chemins pour la circulation des flux. Une nouvelle architecture, au mode d'exploitation partiellement bouclé, est ainsi proposée et validée par des études technicoéconomiques et des tests stochastiques. Cette architecture permet d'augmenter l'insertion de production décentralisée dans le réseau à un coût compétitif tout en garantissant les critères de fiabilité du distributeur.