L'optimisation est un concept fondamental dans beaucoup de domaines scientifiques comme l'informatique, la théorie de l'information, les sciences de l'ingénieur et la physique statistique, ainsi que pour la biologie et les sciences sociales. Un problème d'optimisation met typiquement en jeu un nombre important de variables et une fonction de coût qui dépend de ces variables. La classe des problèmes NP-complets est particulièrement difficile, et il est communément admis que, dans le pire des cas, un nombre d'opérations exponentiel dans la taille du problème est nécessaire pour minimiser la fonction de coût. Cependant, même ces problèmes peuveut être faciles à résoudre en pratique. La question principale considérée dans cette thèse est comment reconnaître si un problème de satisfaction de contraintes NP-complet est "typiquement" difficile et quelles sont les raisons pour cela ? Nous suivons une approche inspirée par la physique statistique des systèmes désordonnés, en particulier la méthode de la cavité développée originalement pour les systèmes vitreux. Nous décrivons les propriétés de l'espace des solutions dans deux des problèmes de satisfaction les plus étudiés : la satisfiabilité et le coloriage aléatoire. Nous suggérons une relation entre l'existence de variables dites "gelées" et la difficulté algorithmique d'un problème donné. Nous introduisons aussi une nouvelle classe de problèmes, que nous appelons "problèmes verrouillés", qui présentent l'avantage d'être à la fois facilement résoluble analytiquement, du point de vue du comportement moyen, mais également extrêmement difficiles du point de vue de la recherche de solutions dans un cas donné.

La thèse se situe dans le domaine de l'optimisation combinatoire, en particulier celui de la<br />modélisation et de la résolution algorithmique. Dans cette thèse, nous étudions deux variantes<br />NP-difficiles de problèmes de type sac-à-dos. Plus précisément, nous traitons le problème de<br />la distribution équitable (le Knapsack Sharing Problem : KSP) et le problème du sac-à-dos<br />généralisé à choix multiple (le Multiple-choice Multidimensional Knapasck Problem : MMKP).<br />Dans la première partie de cette thèse, nous nous intéressons au développement d'algorithmes<br />approchés pour les deux variantes évoquées du problème de type sac-à-dos. La deuxième partie<br />traite essentiellement de la résolution exacte du problème du sac-à-dos généralisé à choix multiple.<br />L'approche exacte que nous proposons est de type séparation et évaluation s'appuyant<br />principalement sur : (i) le calcul des bornes inférieure et supérieure et (ii) l'utilisation de la<br />stratégie par le meilleur d'abord en développant des branches à double noeuds fils et frère.<br />La première partie porte sur l'étude et la résolution approchée des deux problèmes KSP et<br />MMKP. Concernant le problème de la distribution équitable, nous proposons dans un premier<br />temps, une première version de l'algorithme exploitant certaines caractéristiques de la<br />recherche tabou. Dans un deuxième temps, nous développons une deuxième version de l'algorithme dont l'idée principale consiste à tenter de combiner l'intensification de la recherche dans l'espace des solutions et la diversification de la solution obtenue. Nous soulignons la rapidité<br />de la première version et l'efficacité de la deuxième. Ensuite nous nous intéressons au problème<br />de sac-à-dos généralisé à choix multiple. Nous proposons deux heuristiques de recherche locale<br />itérative. Le premier algorithme s'appuie sur une “recherche guidée”. Le deuxième algorithme<br />est une recherche locale que nous appelons réactive avec stratégies de déblocage et de dégradtion améliorantes de la solution et basées sur l'inter-change local.<br /><br />Dans la deuxième partie de cette thèse, nous proposons une méthode de résolution exacte de type séparation et évaluation pour le problème du sac-à-dos généralisé à choix multiple. D'une part, nous nous proposons la réduction du problème initial au problème auxiliaire MMKPaux qui n'est autre que le problème de sac-à-dos à choix multiple MCKP. Nous calculons une borne supérieure pour le MMKPaux et nous établissons le résultat théorique pour lequel une borne supérieure pour le MMKPaux est une borne supérieure pour le MMKP. D'autre part, nous proposons le calcul d'une borne supérieure ainsi qu'une borne inférieure de départ pour le problème étudié qui sont nécessaires pour la réduction de l'espace de recherche. L'étude expérimentale montre l'efficacité de la méthode proposée sur différents groupes d'instances de petite et moyenne taille.<br /><br />Nous expliquons enfin pourquoi cet algorithme exact atteint ses limites de résolution, dˆues<br />principalement à la complexité intrinsèque du modèle étudié. D'autant la résolution dépend de<br />la taille et la densité des instances traitées.

Les problèmes d'optimisation combinatoires définis sur graphes aléatoires sont au coeur de la théorie de la complexité algorithmique. Ils sont également étroitement liés à une formulation champ moyen, dite approximation de Bethe, de modèles sur réseau de verres de spins et verres structuraux. Cette thèse s'appuie sur ce parallèle pour appliquer à des problèmes d'optimisation une approche issue de la physique statistique des systèmes désordonnés, la méthode de la cavité. Etant donné un ensemble d'entrées (instances) d'un problème d'optimisation, cette méthode permet de déterminer les propriétés des solutions des instances typiques, ainsi que celles des instances atypiques, dont les probabilités sont exponentiellement petites (grandes déviations sur la structure externe). Pour une instance donnée, la méthode de la cavité donne également accès à la thermodynamique des différentes solutions admissibles (grandes déviations sur la structure interne). D'un point de vue physique, de nombreux problèmes algorithmiquement difficiles se révèlent ainsi posséder une phase de type verre. Cette thèse est composée de trois parties destinées à exposer les principes, applications et limitations de la méthode de la cavité. La première partie rappelle, dans la perspective des grandes déviations, les liens entre physique statistique et optimisation combinatoire. La deuxième partie aborde les modèles définis sur graphes aléatoires et, pour différents ensembles de graphes, analyse les propriétés typiques et atypiques de ces modèles. La troisième partie est consacrée aux grandes déviations sur le "désordre interne", constitué par les solutions et quasi-solutions d'une instance donnée. Une attention particulière est dévolue au traitement des phases vitreuses où l'ensemble des solutions est fragmenté en un nombre exponentiel d'amas disjoints (structure dite à un pas de brisure de symétrie des répliques); il est montré comment la méthode de la cavité fournit dans de tels cas une description fine des propriétés géométriques de l'espace des solutions.

Cette these est consacree a l'etude des proprietes dynamiques des modeles dilues. Ces derniers sont des systemes de physique statistique de type champ moyen, mais dont la connectivite locale est finie. Leur etude est notamment motivee par l'etroite analogie qui les relient aux problemes d'optimisation combinatoire, la K-satisfiabilite aleatoire par exemple. On expose plusieurs approches analytiques visant a decrire le regime hors d'equilibre de ces systemes, qu'il soit du a une divergence des temps de relaxation dans une phase vitreuse, a l'absence de condition de balance detaillee pour un algorithme d'optimisation, ou a une preparation initiale dans une configuration loin de l'equilibre pour un ferromagnetique. Au cours de ces etudes on rencontrera egalement un probleme de matrices aleatoires, et une generalisation du theoreme de fluctuation-dissipation aux fonctions a n temps.

Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leur déploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers.

La conception des machines électriques a une longue tradition et l'approche " business as usual " est un processus itératif d'essais et d'erreur, certes convergent mais nécessairement stoppé prématurément, car trop couteux. Un perfectionnement récent a consisté à remplacer les prototypes et les maquettes par des prototypes virtuels, entièrement numériques, comme ceux fournis par la méthode des éléments finis. Néanmoins, le procédé s'arrête toujours sur une frustration car le concepteur n'est jamais sûr d'avoir exploré complètement l'espace de conception qui s'offre à lui. La démarche de conception optimale se propose d'améliorer ce processus en le guidant, c'est-à-dire en proposant une méthodologie, et en l'automatisant, c'est-à-dire en proposant des outils logiciels. Mais dans cette démarche apparaissent de nombreuses difficultés. Ainsi, les objectifs généraux de cette thèse sont multiples. Il s'agit de définir des problèmes d'optimisation spécifiques représentatifs des choix structurels et d'élaborer des benchmarks de référence : discret, multiphysique, multidisciplinaire, multi-objectif et multi-niveaux. Ensuite, il faut rechercher, adapter et qualifier les méthodes d'optimisation les mieux à même de résoudre ces problèmes. Enfin, les différentes méthodes d'optimisation proposées sont implantées et testées de façon à prouver leur efficacité et leur adaptation. Un objectif secondaire mais important est de les capitaliser et diffuser les connaissances élaborées

Les approches markoviennes en imagerie et vision par ordinateur offrent un cadre mathématique élégant pour résoudre certains problèmes complexes. Le plus souvent, la fonction d'énergie globale modélisant le problème demeure difficile à minimiser. La première contribution de cette thèse consiste alors à proposer des algorithmes d'optimisation efficace de la classe d'énergies markoviennes multi-étiquettes de premier ordre ayant une attache aux données quelconque et un a priori convexe. Les algorithmes proposés reposent sur la technique de coupe-minimum sur graphe et des stratégies d'optimisation itérative par des nouveaux mouvements de partitions larges et multi-étiquettes, qui permettent d'avoir un compromis entre la qualité de l'optimum atteint et la complexité algorithmique. Le cadre applicatif principal de cette thèse est la reconstruction du relief par interférométrie radar à synthèse d'ouverture. Cette méthode de calcul de modèles numériques de terrain est confrontée le plus souvent à la nature très bruitée des données radar et aussi à la complexité des scènes naturelles et urbaines à reconstruire et à leur grande dimension. Ainsi, la seconde contribution de ces travaux de thèse consiste à proposer des modèles markoviens robustes face à la diversité des scènes à reconstruire dans le cas général et des algorithmes d'optimisation qui leur sont appropriés. L'approche générale est testée et validée sur un jeu de données radar synthétiques et réelles (ERS et ESAR).

Le contexte général de mes travaux se situe dans les réseaux orientés connexions, que ce soit des réseaux optiques à multiplexage en longueur d'onde (WDM), des réseaux MPLS (multi-protocol label switching), ou encore des réseaux à faisceaux hertziens (wireless backhaul networks). Dans ces réseaux, je m'intéresse à router les flux d'information, à agréger des flux d'information bas débits dans des flux de plus hauts débits, à faire évoluer le routage en cas de variations dans la quantité de trafic à transporter ou dans la topologie du réseau, et à assurer la continuité du trafic en cas de panne simple ou multiple. Pour aborder ces questions, j'utilise des outils variés de l'algorithmique, de la théorie des graphes et de l'optimisation combinatoire.<br /> L'ensemble des résultats présentés dans ce document est le fruit de travaux collaboratifs avec les membres de l'équipe-projet MASCOTTE, des collègues d'autres universités, française ou étrangères, et des collègues de France Télécom, Alcatel-Lucent et 3Roam. L'introduction de ce manuscrit résume nos travaux sur le routage, le groupage de trafic, la tolérance aux pannes et la reconfiguration, ainsi que des travaux plus récents sur la minimisation du nombre d'étiquettes dans les réseaux MPLS, le dimensionnement de réseaux de collecte IP sans fil, et sur le routage disjoints d'ensembles particuliers de requêtes. Ensuite, je détaille nos travaux sur le groupage de trafic au travers d'un état de l'art dans le chapitre 3, nos contributions sur la notion de groupes de ressources partageant un risque dans le chapitre 4, et sur la reconfiguration de routages dans le chapitre 5. Le chapitre 6 conclut ce manuscrit en présentant avec quelques directions de recherches.

L'isomorphisme inexact de graphes est un problème crucial pour la définition d'une distance entre graphes, préalable nécessaire à une multitude d'applications allant de l'analyse d'images à des applications biomédicales en passant par la reconnaissance optique de caractères. Ce problème est encore plus complexe que celui de l'isomorphisme exact. Alors que ce dernier est un problème de décision de complexité au moins de classe P et qui ne s'applique qu'à des graphes exactement identiques, l'isomorphisme inexact est un problème combinatoire de complexité de classe NP qui permet de prendre en compte des perturbations dues au bruit, qui apparaissent fréquemment dans les applications réelles. Dans ce cadre, nous choisissons d'étudier une solution basée sur les algorithmes génétiques pouvant être appliquée à l'isomorphisme exact et inexact. Nous proposons des opérateurs de croisement généraux pour tout problème représenté par un codage de permutation, ainsi que des opérateurs spécifiques à l'isomorphisme de graphes qui exploitent une heuristique gloutonne. Nous réalisons une étude exhaustive pour comparer ces opérateurs avec les opérateurs existants, soulignant leurs propriétés, avantages et inconvénients respectifs. Nous étudions par ailleurs plusieurs pistes d'amélioration de l'algorithme, en théorie ou en pratique, considérant successivement les objectifs d'accélération de l'exécution, d'augmentation de la précision et de garantie de résultat optimal. Nous proposons pour cela de combiner l'approche proposée avec d'autres techniques telles que des heuristiques générales comme la recherche locale, des heuristiques dédiées comme l'algorithme A*, et des outils pratiques comme la parallélisation. Ces travaux conduisent à la définition d'une méthode générique pour la résolution de tous les problèmes d'isomorphismes de graphes, qu'il s'agisse d'isomorphismes exact ou inexact, d'isomorphismes de graphes de même taille ou d'isomorphismes de sous-graphes. Nous illustrons enfin la validité de cette solution générale par trois applications concrètes issues de domaines différents, la recherche d'images et la chimie, qui présentent chacune des caractéristiques spécifiques, utilisant des graphes attribués ou non, soumis aux perturbations plutôt structurelles ou au niveau d'attributs.

Ce travail porte sur la résolution exacte d'un problème d'optimisation combinatoire multi-objectif. Nous cherchons d'une part à confirmer l'efficacité de l'algorithme dit en deux phases, et d'autre part à poser une généralisation des procédures de séparation et évaluation, populaires dans le cadre mono-objectif mais presque absentes en multi-objectif. Notre étude s'appuie sur le problème multi-objectif de sac à dos unidimensionnel en variables binaires. Ce dernier est un classique de l'optimisation combinatoire, présent comme sous problème dans de nombreux problèmes d'optimisation. La première partie de nos travaux porte sur un pré-traitement permettant de réduire la taille d'instances de ce problème. Nous mettons en évidence plusieurs propriétés permettant de déterminer a priori une partie de la structure de toutes les solutions efficaces. Nous nous attachons ensuite à décrire une procédure performante de type deux phases pour ce problème, tout d'abord dans le cas bi-objectif. Nous étendons ensuite cette procédure pour des instances ayant trois objectifs ou plus. Les résultats obtenus sont comparés aux meilleurs algorithmes existants pour ce problème et confirment l'efficacité de l'approche en deux phases. La dernière partie de notre travail concerne la généralisation au cas multi-objectif d'une procédure de séparation et évaluation. Nous identifions plusieurs difficultés auxquelles nous répondons en proposant deux nouvelles procédures. Les expérimentations numériques indiquent que ces dernières permettent de résoudre des instances en des temps raisonnables, bien qu'elles n'atteignent pas les performances d'une procédure de type deux phases.