A cause de leur aspect strat égique et des divers challenges qu'ils repr ésentent en termes de mod élisation et de r ésolution, les probl èmes de localisation et de conception de r éseaux ont été largement étudi es par les sp écialistes en recherche opérationnelle. Par ailleurs, bien que les études de cas dans ce domaine soient rares dans la litt érature, plusieurs travaux r écents ont int égr é certains aspects op érationnels afi n de rendre ces probl èmes d'optimisation plus r éalistes. L'objet de notre projet de recherche est le d éveloppement d'un mod èle de conception d'un r éseau de distribution prenant en compte plusieurs aspects op érationnels inspir és d'une étude de cas dans le domaine de l'automobile. Bien que nos choix de mod élisation soient motiv és par cette étude de cas, ils restent applicables dans d'autres secteurs industriels. Le r éseau de distribution consid ér é se compose de trois niveaux : les usines au premier niveau, les centres de distribution (CD) au deuxi ème niveau et les clients au dernier niveau. Nous supposons que le nombre et la localisation des usines ainsi que le nombre et la localisation des clients sont connus. Etant donn é la demande des clients et une liste de CD potentiels, l'objectif est de d éterminer la localisation des CD a ouvrir et d'y a ffecter les clients de mani ère a minimiser le coût total. Nos contributions par rapport aux travaux existants concernent la mod élisation et la r ésolution du probl ème ainsi que les tests num ériques eff ectu és. En termes de mod élisation, nous consid érons divers aspects op érationnels qui ont été pris en compte s épar ément dans la litt érature mais jamais combin és dans un même mod èle. Plus particuli èrement, nous introduisons un "clustering" en pr étraitement afi n de mod éliser les tourn ées de camions. Nous int égrons également des contraintes de volume minimum sur les axes de transport pour assurer l'utilisation de camions pleins, des contraintes de volume minimum et de capacit é maximale sur les centres de distribution, des contraintes de distance de couverture maximale et des contraintes d'uni-aff ectation. Par ailleurs, nous étudions une extension multi-p ériodes du probl ème en utilisant un "clustering" dynamique pour mod éliser des tourn ées de camions multi-p ériodes. En termes de r ésolution, comme le probl ème étudi é est NP-di ffcile au sens fort, nous proposons di fférentes m éthodes heuristiques performantes bas ées sur la relaxation lin éaire. A travers les tests eff ectu és, nous montrons que ces m éthodes fournissent des solutions proches de l'optimale en moins de temps de calcul que l'application directe d'un solveur lin éaire. Nous analysons également la structure des r éseaux de distribution obtenus et nous comparons les r ésultats issus de plusieurs versions du mod èle afi n de montrer la valeur ajout ée du "clustering" ainsi que de l'approche multi-p ériodes.

Les problèmes d'optimisation combinatoire sont généralement NP-difficiles et les méthodes exactes demeurent inefficaces pour les résoudre rapidement. Les métaheuristiques sont des méthodes génériques de résolution connues et utilisées pour leur efficacité. Elles possèdent souvent plusieurs paramètres qui s'avèrent fastidieux à régler pour obtenir de bonnes performances. Il est alors intéressant de chercher à rendre plus évident, voire à automatiser, ce réglage des paramètres. Le paysage d'un problème d'optimisation combinatoire est une structure, basée sur la notion de voisinage, permettant de caractériser le problème puis de suivre la dynamique d'une méthode d'optimisation pour comprendre son efficacité. Les travaux de cette thèse portent sur l'analyse de paysage de problèmes d'optimisation combinatoire et le lien étroit avec certaines classes de métaheuristiques, basées sur une exploration du voisinage des solutions. Ainsi, nous montrons l'influence de la structure de paysage sur la dynamique d'une métaheuristique, pour deux problèmes issus de la logistique. Ensuite, nous analysons les caractéristiques du paysage qui permettent de concevoir et/ou paramétrer des métaheuristiques, principalement des recherches locales, efficaces. La neutralité est, en particulier, une caractéristique structurelle importante des paysages. De tels paysages présentent de nombreux plateaux bloquant la progression d'une recherche locale. Après une analyse fine des plateaux, nous prouvons que cette structure neutre ne doit pas être ignorée. Puis, nous utilisons plusieurs informations liées à la neutralité, et plus particulièrement aux plateaux bloquants, pour concevoir une première recherche locale simple à mettre en œuvre et efficace. Enfin, pour approfondir nos travaux sur les structures neutres, nous avons choisi d'exploiter la neutralité à tous les niveaux du paysage pour concevoir une nouvelle recherche locale basée sur la capacité des solutions d'un même plateau à produire une amélioration. Une stratégie de guidage vers cette solution est alors proposée. La thèse se termine par l'analyse comparative des deux méthodes d'optimisation proposées pour les problèmes neutres afin d'en exploiter de nouvelles caractéristiques, et ainsi, renforcer le lien entre l'analyse de paysage et la conception de méthodes efficaces.

Nous nous plaçons dans le cadre de l'analyse statique de programmes, et nous nous intéressons aux propriétés numériques, c'est a dire celles qui concernent les valeurs numériques des variables de programmes. Nous essayons en particulier de déterminer une sur-approximation garantie de l'ensemble de valeurs possibles pour chaque variable numérique utilisée dans le programme à analyser. Cette analyse statique est faite dans le cadre de la théorie de l'interprétation abstraite, théorie présentant un compromis entre les limites théoriques d'indécidabilite et de calculabilite et la précision des résultats obtenus. Nous sommes partis des travaux d'Eric Goubault et Sylvie Putot, que nous avons étendus et généralisés. Notre nouveau domaine abstrait, appelé ensembles affines contraints, combine à la fois l'efficacite de calcul des domaines à base de formes affines et le pouvoir ex- pressif des domaines relationnels classiques tels que les octogones ou les polyèdres. Le nouveau domaine a été implémenté pour mettre en évidence l'intérêt de cette combinaison, ses avantages, ses performances et ses limites par rapport aux autres domaines numériques déjà existants. Le formalisme ainsi que les résultats pra- tiques ont fait l'objet de plusieurs publications [CAV 2009, CAV 2010].

Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources... Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été appliquée sur deux types de problèmes. Le premier est l'affectation des fréquences (FAP) dans les réseaux de radiocommunications militaires, en particulier les problèmes proposés de 1993 (instances du projet européen CALMA) jusqu'à 2010 (instances d'un projet DGA). Le deuxième est le problème académique de k-coloration de graphes sur les instances DIMACS. La méthode a amélioré quelques meilleurs scores connus actuellement. Dans les deux problèmes nous avons traité des contraintes unaires et binaires, ainsi que des contraintes n-aires et de l'optimisation de fonction sous contraintes pour le FAP. Les principes de Tabu-NG sont généraux et elle peut s'appliquer sur d'autres CSP. Elle peut par ailleurs accueillir des heuristiques spécifiques aux problèmes, nous l'avons pratiqué sur les problèmes cités, et en ce sens nous pensons pouvoir qualifier la méthode de métaheuristique sans abuser de cette définition.

La résolution exacte de problèmes d'optimisation combinatoire avec les algorithmes Branch and Bound (B&B) nécessite un nombre exorbitant de ressources de calcul. Actuellement, cette puissance est offerte par les environnements large échelle comme les grilles de calcul. Cependant, les grilles présentent de nouveaux challenges : le passage à l'échelle, l'hétérogénéité et la tolérance aux pannes. La majorité des algorithmes B&B revisités pour les grilles de calcul sont basés sur le paradigme Master-Worker, ce qui limite leur passage à l'échelle. De plus, la tolérance aux pannes est rarement adressée dans ces travaux. Dans cette thèse, nous proposons trois principales contributions : P2P-B&B, H-B&B et FTH-B&B. P2P-B&B est un famework basé sur le paradigme Master-Worker traite le passage à l'échelle par la réduction de la fréquence de requêtes de tâches et en permettant les communications directes entre les workers. H-B&B traite aussi le passage à l'échelle. Contrairement aux approches proposées dans la littérature, H-B&B est complètement dynamique et adaptatif i.e. prenant en compte l'acquisition dynamique des ressources de calcul. FTH-B&B est basé sur de nouveaux méchanismes de tolérance aux pannes permettant de construire et maintenir la hiérarchie équilibrée, et de minimiser la redondance de travail quand les tâches sont sauvegardées et restaurées. Les approches proposées ont été implémentées avec la plateforme pour grille ProActive et ont été appliquées au problème d'ordonnancement de type Flow-Shop. Les expérimentations large échelle effectuées sur la grille Grid'5000 ont prouvé l'éfficacité des approches proposées.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d'origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d'ordonnancement cumulatif. Un problème d'ordonnancement consiste à déterminer les dates de débuts et de fins d'un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l'on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l'on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l'aide d'algorithmes dédiés et de métaheuristiques. Par exemple, l'utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d'ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l'idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d'accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appe- lées à chaque noeud de l'arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d'un million de tâches et 64 resources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes de placement et d'ordonnancement.

Les données médicales souffrent de problèmes d'uniformisation ou d'incertitude, ce qui les rend difficilement utilisables directement par des logiciels médicaux, en particulier dans le cas du recrutement pour les essais cliniques. Dans cette thèse, nous proposons une approche permettant de palier la mauvaise qualité de ces données à l'aide de méthodes de classification supervisée. Nous nous intéresserons en particulier à 3 caractéristiques de ces données : asymétrie, incertitude et volumétrie. Nous proposons l'algorithme MOCA-I qui aborde ce problème combinatoire de classification partielle sur données asymétriques sous la forme d'un problème de recherche locale multi-objectif. Après avoir confirmé les apports de la modélisation multi-objectif dans ce contexte, nous calibrons MOCA-I et le comparons aux meilleurs algorithmes de classification de la littérature, sur des jeux de données réels et asymétriques de la littérature. Les ensembles de règles obtenus par MOCA-I sont statistiquement plus performants que ceux de la littérature, et 2 à 6 fois plus compacts. Pour les données ne présentant pas d'asymétrie, nous proposons l'algorithme MOCA, statistiquement équivalent à ceux de la littérature. Nous analysons ensuite l'impact de l'asymétrie sur le comportement de MOCA et MOCA-I, de manière théorique et expérimentale. Puis, nous proposons et évaluons différentes méthodes pour traiter les nombreuses solutions Pareto générées par MOCA-I, afin d'assister l'utilisateur dans le choix de la solution finale et réduire le phénomène de sur-apprentissage. Enfin, nous montrons comment le travail réalisé peut s'intégrer dans une solution logicielle.

Le développement des technologies de séquençage et de génotypage haut-débit permet de mesurer, pour un individu, une grande quantité d'information génomique. L'objectif de ce travail est, dans le cadre de la sélection génomique animale, de sélectionner un sous-ensemble de marqueurs génétiques pertinents permettant de prédire un caractère quantitatif, dans un contexte où le nombre d'animaux génotypés est largement inférieur au nombre de marqueurs étudiées. Ce manuscrit présente un état de l'art des méthodes actuelles permettant de répondre à la problématique. Nous proposons ensuite de répondre à notre problématique de sélection de variables en régression en grande dimension en combinant approches d'optimisation combinatoire et modèles statistiques. Nous commençons par paramétrer expérimentalement deux méthodes d'optimisation combinatoire, la recherche locale itérée et l'algorithme génétique, combinées avec une régression li- néaire multiple et nous évaluons leur pertinence. Dans le contexte de la génomique animale les relations familiales entre animaux sont connues et peuvent constituer une information importante. Notre approche étant flexible, nous proposons une adapta- tion permettant de prendre en considération ces relations familiales via l'utilisation d'un modèle mixte. Le problème du sur-apprentissage étant particulièrement présent sur nos données dû au déséquilibre important entre le nombre de variables étudiées et le nombre d'animaux disponibles, nous proposons également une amélioration de notre approche permettant de diminuer ce sur-apprentissage. Les différentes approches proposées sont validées sur des données de la littérature ainsi que sur des données réelles de Gènes Diffusion.

Le calcul de la fiabilité des réseaux est en général un problème NP-difficile. On peut par exemple, s'intéresser à la fiabilité des systèmes de télécommunications où l'on veut évaluer la probabilité qu'un groupe sélectionné de noeuds (qui peut être juste une paire) puissent communiquer, ou s'intéresser aux systèmes d'alimentation électriques où l'on veut estimer le risque que l'électricité n'est pas fournie à certains noeuds, ou encore, étudier la fiabilité des systèmes de transport, où les liens représentent les routes et sont soumis à des dommages. Dans tous ces cas, un ensemble de noeuds déconnectés peut avoir des conséquences critiques, que ce soit financières ou au niveau de la sécurité. Une estimation précise de la fiabilité est ainsi nécessaire. Les réseaux de communication moderne se caractérisent par leur grande taille, donc l'estimation via la simulation de Monte Carlo devient souvent un choix favorable. Un algorithme de Monte Carlo sous sa forme standard, échantillonne N réalisations du graphe (représentant le réseau) indépendantes, et la défiabilité est estimée à partir de la proportion des N réalisations pour lesquelles les noeuds sélectionnés ne sont pas connectés. Dans ces réseaux, les probabilités de défaillance des liens (arcs) sont généralement petites et donc les pannes d'un réseau deviennent des événements rares. Cela pose un défi majeur pour estimer la fiabilité d'un réseau. Dans cette thèse, nous présentons différentes techniques basées sur l'échantillonnage préférentiel (Importance Sampling en anglais IS), pour l'estimation de la fiabilité d'un réseau. Grace à cette technique les probabilités originales d'échantillonnage des arcs sont remplacées par de nouvelles probabilités, puis multiplier l'ancien estimateur par le quotient de vraisemblance (likelihood ratio) pour rester sans biais. On s'intéresse tout particulièrement à l'étude et au calcul de la fiabilité des réseaux hautement fiables et représentés par des graphes statiques. Dans ce cas la défiabilité est très petite, parfois de l'ordre de 10−10, ce qui rend l'approche standard de Monte Carlo inutile, car pour pouvoir estimer cette probabilité il nous faut un échantillon de taille supérieure à dix milliards. Pour une bonne estimation de la fiabilité des réseaux au moindre coût, nous avons étudié, analysé et développé les points suivants : - En premier lieu nous avons développé une méthode basée sur l'échantillonnage préférentiel. Le processus d'échantillonnage de tous les arcs du graphe sous la nouvelle probabilité est représenté par une chaîne de Markov, telle qu'à chaque étape on détermine l'état d'un arc avec une nouvelle probabilité déterminée en fonction de l'état de tous les arcs précédemment échantillonnés. Les fonctions valeurs de la nouvelle probabilité sont approchées par les coupes minimales possédant la plus grande probabilité de défiabilité, elle est le produit des défiabilités des arcs de la coupe. Des preuves de bonnes propriétés de l'estimateur basé sur l'échantillonnage préférentiel sont faites. - Un deuxième point a été abordé et développé, consiste à appliquer des techniques de réduction série-parallèle à chaque étape de l'échantillonnage IS précédemment décrit, afin de réduire substantiellement et la variance et le temps de simulation. - Le dernier point consiste à combiner pour approximation de l'estimateur à variance nulle, l'approximation de la défiabilité par une coupe minimale qui sous-estime la défiabilité avec une autre approximation basée sur les chemins minimaux qui la sur-estime. Des algorithmes d'optimisation sont utilisés pour rechercher le facteur optimal d'ajustement des deux approximations pour minimiser la variance.

Les problèmes d'optimisation spatialisés font intervenir des entités (clients, demandes, trafic) réparties sur une étendue (la donnée) et des dispositifs physiques (antennes, véhicules) qui doivent leur être associés de manière optimale. Il en résulte de nombreux problèmes d'optimisation combinatoire difficile à résoudre (NP-hard). Pour résoudre ce type de problème, nous proposons des algorithmes à structure intermédiaire, des recherches locales et des approches de résolution collective selon des métaphores de systèmes naturels et biologiques. Le but est par exemple de prendre en compte dès le départ la potentialité d'application à des problèmes dynamiques, de fournir un canevas à la mise en œuvre distribuée possible des algorithmes, et de résoudre des problèmes de grandes tailles.