Dans ce mémoire, nous présentons un nouveau type de problème de confection de tour- née pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivée par des problèmes similaires rapportés dans la littérature. Le véhi- cule en question contient plusieurs piles où des colis de hauteurs différentes sont empilés durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut dépasser une certaine hauteur maximale. Aucun déplacement n’est permis lors de la li- vraison d’un colis, ce qui signifie que le colis doit être sur le dessus d’une pile au moment d’être livré. De plus, tout colis i ramassé avant un colis j et contenu dans la même pile doit être livré après j. Une heuristique à grand voisinage, basé sur des travaux récents dans le domaine, est proposée comme méthode de résolution. Des résultats numériques sont rapportés pour plusieurs instances classiques ainsi que pour de nouvelles instances. / In this work, we consider a new type of pickup and delivery routing problem with last- in-first-out loading constraints for a single vehicle with multiple stacks. This problem is motivated by similar problems reported in the literature. In the problem considered, items are collected and put on top of one of multiple stacks inside the vehicle, such that the total height of the items on each stack does not exceed a given threshold. The loading constraints state that if items i and j are in the same stack and item i is collected before item j, then i must be delivered after j. Furthermore, an item can be delivered only if it is on the top of a stack. An adaptive large neighborhood heuristic, based on recent studies in this field, is proposed to solve the problem. Numerical results are reported on many classical instances reported in the literature and also on some new ones.

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.

Cette thèse étudie une approche intégrant la gestion de l’horaire et la conception de réseaux de services pour le transport ferroviaire de marchandises. Le transport par rail s’articule autour d’une structure à deux niveaux de consolidation où l’affectation des wagons aux blocs ainsi que des blocs aux services représentent des décisions qui complexifient grandement la gestion des opérations. Dans cette thèse, les deux processus de consolidation ainsi que l’horaire d’exploitation sont étudiés simultanément. La résolution de ce problème permet d’identifier un plan d’exploitation rentable comprenant les politiques de blocage, le routage et l’horaire des trains, de même que l’habillage ainsi que l’affectation du traffic. Afin de décrire les différentes activités ferroviaires au niveau tactique, nous étendons le réseau physique et construisons une structure de réseau espace-temps comprenant trois couches dans lequel la dimension liée au temps prend en considération les impacts temporels sur les opérations. De plus, les opérations relatives aux trains, blocs et wagons sont décrites par différentes couches. Sur la base de cette structure de réseau, nous modélisons ce problème de planification ferroviaire comme un problème de conception de réseaux de services. Le modèle proposé se formule comme un programme mathématique en variables mixtes. Ce dernie r s’avère très difficile à résoudre en raison de la grande taille des instances traitées et de sa complexité intrinsèque. Trois versions sont étudiées : le modèle simplifié (comprenant des services directs uniquement), le modèle complet (comprenant des services directs et multi-arrêts), ainsi qu’un modèle complet à très grande échelle. Plusieurs heuristiques sont développées afin d’obtenir de bonnes solutions en des temps de calcul raisonnables. Premièrement, un cas particulier avec services directs est analysé. En considérant une cara ctéristique spécifique du problème de conception de réseaux de services directs nous développons un nouvel algorithme de recherche avec tabous. Un voisinage par cycles est privilégié à cet effet. Celui-ci est basé sur la distribution du flot circulant sur les blocs selon les cycles issus du réseau résiduel. Un algorithme basé sur l’ajustement de pente est développé pour le modèle complet, et nous proposons une nouvelle méthode, appelée recherche ellipsoidale, permettant d’améliorer davantage la qualité de la solution. La recherche ellipsoidale combine les bonnes solutions admissibles générées par l’algorithme d’ajustement de pente, et regroupe les caractéristiques des bonnes solutions afin de créer un problème élite qui est résolu de facon exacte à l’aide d’un logiciel commercial. L’heuristique tire donc avantage de la vitesse de convergence de l’algorithme d’ajustement de pente et de la qualité de solution de la recherche ellipsoidale. Les tests numériques illustrent l’efficacité de l’heuristique proposée. En outre, l’algorithme représente une alternative intéressante afin de résoudre le problème simplifié. Enfin, nous étudions le modèle complet à très grande échelle. Une heuristique hybride est développée en intégrant les idées de l’algorithme précédemment décrit et la génération de colonnes. Nous proposons une nouvelle procédure d’ajustement de pente où, par rapport à l’ancienne, seule l’approximation des couts liés aux services est considérée. La nouvelle approche d’ajustement de pente sépare ainsi les décisions associées aux blocs et aux services afin de fournir une décomposition naturelle du problème. Les résultats numériques obtenus montrent que l’algorithme est en mesure d’identifier des solutions de qualité dans un contexte visant la résolution d’instances réelles. / This thesis studies a scheduled service network design problem for rail freight transportation planning. Rails follow a special two level consolidation organization, and the car-to-block, block-to-service handling procedure complicates daily operations. In this research, the two consolidation processes as well as the operation schedule are considered simultaneously, and by solving this problem, we provide an overall cost-effective operating plan, including blocking policy, train routing, scheduling, make-up policy and traffic distribution. In order to describe various rail operations at the tactical level, we extend the physical network and construct a 3-layer time-space structure, in which the time dimension takes into consideration the temporal impacts on operations. Furthermore, operations on trains, blocks, and cars are described in different layers. Based on this network structure, we model the rail planning problem to a service network design formulation. The proposed model relies on a complex mixed-integer programming formulation. The problem is very hard to solve due to the computational difficulty as well as the tremendous size of the application instances. Three versions of the problem are studied, which are the simplified model (with only non-stop services), complete model (with both non-stop and multi-stop services) and very-large-scale complete model. Heuristic algorithms are developed to provide good feasible solutions in reasonable computing efforts. A special case with non-stop services is first studied. According to a specific characteristic of the direct service network design problem, we develop a tabu search algorithm. The tabu search moves in a cycle-based neighborhood, where flows on blocks are re-distributed according to the cycles in a conceptual residual network. A slope scaling based algorithm is developed for the complete model, and we propose a new method, called ellipsoidal search, to further improve the solution quality. Ellipsoidal search combines the good feasible solutions generated from the slope scaling, and collects the features of good solutions into an elite problem, and solves it with exact solvers. The algorithm thus takes advantage of the convergence speed of slope scaling and solution quality of ellipsoidal search, and is proven effective. The algorithm also presents an alternative for solving the simplified problem. Finally, we work on the very-large-size complete model. A hybrid heuristic is developed by integrating the ideas of previous research with column generation. We propose a new slope scaling scheme where, compared with the previous scheme, only approximate service costs instead of both service and block costs are considered. The new slope scaling scheme thus separates the block decisions and service decisions, and provide a natural decomposition of the problem. Experiments show the algorithm is good to solve real-life size instances.

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides. / Many problems in transportation and logistics can be formulated as network design models. They usually require to transport commodities, passengers or data in a network to satisfy a certain demand while minimizing the costs. In this work, we focus on the multicommodity capacited fixed-charge network design problem which consists of opening a subset of the links in the network to satisfy the demand. Each link has a capacity and a fixed cost that is paid if it is opened. The objective is to minimize the fixed costs of the opened links and the transportation costs of the commodities. We present an exact method to solve this problem based on mixed integer programming techniques. Our method is a specialization of the branch-and-bound algorithm, called branch-and-price-and-cut, in which we use column generation and cutting-plane method to solve large-scale instances. We compare our method with CPLEX, currently one of the best solver. Numerical results show that our method is competitive on medium-scale instances and better on large-scale instances.

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.

Le cloud computing a émergé au cours de la dernière décennie pour être largement adopté aujourd'hui dans plusieurs domaines de l'informatique. Il consiste à proposer des ressources axées, ou non, sur le marché sous forme de services qui peuvent être consommés de manière souple et transparente. Dans cette thèse, nous traitons le problème d'ordonnancement, un des enjeux majeurs du cloud. Selon la configuration de cloud ciblée, nous avons identifié trois niveaux d'ordonnancement : niveau service, niveau tâche et niveau machine virtuelle. Nous revisitons la modélisation du problème, la conception et l'implémentation des métaheuristiques multiobjectives pour chaque niveau d'ordonnancement du cloud. Les ordonnanceurs à base de métaheuristiques que nous proposons portent sur différents critères notamment la consommation d'énergie, les émissions de gaz à effet de serre, le profit et la qualité du service (coût et temps de réponse). Nous prouvons leur capacité d'adaptation aux contraintes du cloud en les intégrant au sein du gestionnaire de cloud OpenNebula. De plus, nos ordonnanceurs ont été largement expérimentés utilisant des configurations réalistes de cloud sur Grid'5000, en tant qu'infrastructure en tant que service (IAAS), et des scénarios concrets basés sur les instances et les tarifications d'Amazon EC2. Les résultats présentés montrent que les méthodes que nous proposons surpassent les approches l'ordonnancement existantes sur tous les critères cités précédemment.

Les grilles de calcul et le "cloud computing" permettent de distribuer un ensemble de ressources informatiques, telles que du stockage ou du temps de calcul, à un ensemble d'utilisateurs en fonction de leurs demandes en donnant l'illusion de ressources infinies. Cependant, lorsque l'ensemble de ces ressources est insuffisant pour satisfaire les exigences des utilisateurs, des conflits d'intérêts surgissent. Ainsi, un libre accès à des ressources limitées peut entraîner une utilisation inefficace qui pénalise l'ensemble des participants. Dans de tels environnements, il devient nécessaire d'établir des procédures d'arbitrage afin de résoudre ces conflits en garantissant une distribution équitable aux différents utilisateurs. Nous présentons une nouvelle classe de problèmes : celle des ordonnancements multi-utilisateurs. Cette thèse aborde la notion d'équité au travers de problèmes d'allocation de ressources sous incertitudes et d'ordonnancement de tâches périodiques.