Le problème de partitionnement de graphe est un problème fondamental en optimisation combinatoire. Le problème revient à décomposer l'ensemble des nœuds d'un graphe en plusieurs sous-ensembles disjoints de nœuds (ou clusters), de sorte que la somme des poids des arêtes dont les extrémités se trouvent dans différents clusters est réduite au minimum. Dans cette thèse, nous étudions le problème de partitionnement de graphes avec des poids (non négatifs) sur les nœuds et un ensemble de contraintes supplémentaires sur les clusters (GPP-SC) précisant que la capacité totale (par exemple, le poids total des nœuds dans un cluster, la capacité totale sur les arêtes ayant au moins une extrémité dans un cluster) de chaque groupe ne doit pas dépasser une limite prédéfinie (appelée limite de capacité). Ceci diffère des variantes du problème de partitionnement de graphe le plus souvent abordées dans la littérature en ce que:_ Le nombre de clusters n'est pas imposé (et fait partie de la solution),_ Les poids des nœuds ne sont pas homogènes.Le sujet de ce travail est motivé par le problème de la répartition des tâches dans les structures multicœurs. Le but est de trouver un placement admissible de toutes les tâches sur les processeurs tout en respectant leur capacité de calcul et de minimiser le volume total de la communication inter-processeur. Ce problème peut être formulé comme un problème de partitionnement de graphe sous contraintes de type sac-à-dos (GPKC) sur des graphes peu denses, un cas particulier de GPP-SC. En outre, dans de telles applications, le cas des incertitudes sur les poids des nœuds (poids qui correspondent par exemple à la durée des tâches) doit être pris en compte.La première contribution de ce travail est de prendre en compte le caractère peu dense des graphes G = (V,E) typiques rencontrés dans nos applications. La plupart des modèles de programmation mathématique existants pour le partitionnement de graphe utilisent O(|V|^3) contraintes métriques pour modéliser les partitions de nœuds et donc supposent implicitement que G est un graphe complet. L'utilisation de ces contraintes métriques dans le cas où G n'est pas complet nécessite l'ajout de contraintes qui peuvent augmenter considérablement la taille du programme. Notre résultat montre que, pour le cas où G est un graphe peu dense, nous pouvons réduire le nombre de contraintes métriques à O(|V||E|) [1], [4]... / The graph partitioning problem is a fundamental problem in combinatorial optimization. The problem refers to partitioning the set of nodes of an edge weighted graph in several disjoint node subsets (or clusters), so that the sum of the weights of the edges whose end-nodes are in different clusters is minimized. In this thesis, we study the graph partitioning problem on graph with (non negative) node weights with additional set constraints on the clusters (GPP-SC) specifying that the total capacity (e.g. the total node weight, the total capacity over the edges having at least one end-node in the cluster) of each cluster should not exceed a specified limit (called capacity limit). This differs from the variants of graph partitioning problem most commonly addressed in the literature in that:-The number of clusters is not imposed (and is part of the solution),-The weights of the nodes are not homogeneous.The subject of the present work is motivated by the task allocation problem in multicore structures. The goal is to find a feasible placement of all tasks to processors while respecting their computing capacity and minimizing the total volume of interprocessor communication. This problem can be formulated as a graph partitioning problem under knapsack constraints (GPKC) on sparse graphs, a special case of GPP-SC. Moreover, in such applications, the case of uncertain node weights (weights correspond for example to task durations) has to be taken into account.The first contribution of the present work is to take into account the sparsity character of the graph G = (V,E). Most existing mathematical programming models for the graph partitioning problem use O(|V|^3) metric constraints to model the partition of nodes and thus implicitly assume that G is a complete graph. Using these metric constraints in the case where G is not complete requires adding edges and constraints which may greatly increase the size of the program. Our result shows that for the case where G is a sparse graph, we can reduce the number of metric constraints to O(|V||E|).The second contribution of present work is to compute lower bounds for large size graphs. We propose a new programming model for the graph partitioning problem that make use of only O(m) variables. The model contains cycle inequalities and all inequalities related to the paths in the graph to formulate the feasible partitions. Since there are an exponential number of constraints, solving the model needs a separation method to speed up the computation times. We propose such a separation method that use an all pair shortest path algorithm thus is polynomial time. Computational results show that our new model and method can give tight lower bounds for large size graphs of thousands of nodes.....

Dans les systèmes cloud géographiquement distribués, un défi majeur auquel sont confrontés les fournisseurs de cloud consiste à optimiser et à configurer leurs infrastructures. En particulier, cela consiste à trouver un emplacement optimal pour les machines virtuelles (VMs) afin de minimiser les coûts tout en garantissant une bonne performance du système. De plus, en raison des fluctuations de la demande et des modèles de trafic, il est essentiel d'ajuster dynamiquement le schéma de placement des VMs en utilisant les techniques de migration des VMs. Cependant, malgré ses avantages apportés, dans le contexte du Cloud géo-distribué, la migration des VMs génère un trafic supplémentaire dans le réseau backbone ce qui engendre la dégradation des performances des applications dans les centres de données (DCs) source et destination. Par conséquent, les décisions de migration doivent être bien étudiés et basées sur des paramètres précis. Dans ce manuscrit, nous étudions les problèmes d'optimisation liés au placement, à la migration et à l'ordonnancement des VMs qui hébergent des applications hautement corrélées et qui peuvent être placés dans des DCs géo-distribués. Dans ce contexte, nous proposons un outil de gestion de DC autonome basé sur des modèles d'optimisation en ligne et hors ligne pour gérer l'infrastructure distribuée du Cloud. Notre objectif est de minimiser le volume du trafic global circulant entre les différents DCs du système.Nous proposons également des modèles d'optimisation stochastiques et déterministes pour traiter les différents modèles de trafic de communication. En outre, nous fournissons des algorithmes quasi-optimaux qui permettent d'avoir la meilleure séquence de migration inter-DC des machines virtuelles inter-communicantes. En plus, nous étudions l'impact de la durée de vie des VMs sur les décisions de migration afin de maintenir la stabilité du Cloud. Enfin, nous utilisons des environnements de simulation pour évaluer et valider notre approche. Les résultats des expériences menées montrent l'efficacité de notre approche / In geo-distributed cloud systems, a key challenge faced by cloud providers is to optimally tune and configure their underlying cloud infrastructure. An important problem in this context, deals with finding an optimal virtual machine (VM) placement, minimizing costs while at the same time ensuring good system performance. Moreover, due to the fluctuations of demand and traffic patterns, it is crucial to dynamically adjust the VM placement scheme over time. Hence, VM migration is used as a tool to cope with this problem. However, despite the benefits brought by VM migration, in geo-distributed cloud context, it generates additional traffic in the backbone links which may affect the application performance in both source and destination DCs. Hence, migration decisions need to be effective and based on accurate parameters. In this work, we study optimization problems related to the placement, migration and scheduling of VMs hosting highly correlated and distributed applications within geo-distributed DCs. In this context, we propose an autonomic DC management tool based on both online and offline optimization models to manage the distributed cloud infrastructure. Our objective is to minimize the overall expected traffic volume circulating between the different DCs of the system. To deal with different types of communication traffic patterns, we propose both deterministic and stochastic optimization models to solve VM placement and migration problem and to cope with the uncertainty of inter-VM traffic. Furthermore, we propose near-optimal algorithms that provide with the best inter-DCs migration sequence of inter-communicating VMs. Along with that, we study the impact of the VM's lifetime on the migration decisions in order to maintain the stability of the cloud system. Finally, to evaluate and validate our approach, we use experimental tests as well as simulation environments. The results of the conducted experiments show the effectiveness of our proposals

Le problème de tournées de véhicules (Vehicle routing problem - VRP), introduit il y a plus de 60 ans, demeure au cœur des systèmes de transport. Après des décennies de développement, le VRP, par son ensemble très riche de variantes, représente l'un des problèmes les plus étudiés dans la littérature. Pourtant, en raison du manque de données, deux hypothèses importantes font que le VRP ne s'adapte pas efficacement au trafic et à la congestion, deux éléments importants pour modéliser de façon réelle des problèmes pratiques. Une première hypothèse considère que la vitesse de déplacement est constante dans le temps. La seconde, considère que chaque paire de nœuds (clients) n'est reliée que par un arc, ignorant le réseau routier implicite (sous-jacent). La congestion de la circulation est l'un des plus grands défis des systèmes de transport. Ces systèmes étant directement affectés par la congestion, l'ensemble de la chaîne d'approvisionnement doit s'adapter à ce facteur, ce qui n'est pas simple. La croissance continue du fret au cours des dernières années aggrave encore la situation et une attention renouvelée à la mobilité, à l'environnement et à la logistique urbaine a mis en lumière ces questions. Récemment, les avancées technologiques en communication et en acquisition de données en temps réel ont permis de collecter plusieurs informations sur les véhicules telles que leur localisation, leur accélération, leur vitesse, leur décélération, etc. Ainsi, nous pouvons remettre en question la façon dont nous définissons, modélisons et résolvons les problèmes de transport. Ceci nous permet de surmonter les deux hypothèses mentionnées en intégrant non seulement les informations relatives à la congestion, mais aussi en considérant l'ensemble du réseau routier. Dans cette thèse nous considérons l'ensemble du réseau routier sous-jacent, ce qui signifie que nous avons les nœuds clients mais également tous les nœuds intermédiaires qui constituent ce réseau. Ensuite, nous modélisons le temps de trajet de chaque route individuellement au cours de la journée. En divisant une journée en petits intervalles, jusqu'à une précision de l'ordre de la seconde, nous prenons en considération des informations précises sur le trafic. Il en résulte un nouveau problème appelé le problème de tournées de véhicules à plus court chemin avec dépendance du temps (Time-dependant shortest path vehicle routing problem - TD-SPVRP), dans lequel nous combinons le problème du plus court chemin avec dépendance du temps et le VRP avec dépendance du temps, créant ainsi un problème plus général et très complexe. Le TD-SPVRP est plus proche des conditions réelles et il constitue le sujet du chapitre 2 où nous le formulons comme un modèle de programmation linéaire en nombres entiers mixtes et concevons une heuristique rapide et efficace pour le résoudre. Nous testons le modèle ainsi que l'heuristique sur des instances générées à partir de données réelles de circulation sur le réseau routier de la ville de Québec, Canada. Les résultats montrent que l'heuristique fournit des solutions de haute qualité avec un écart moyen de 5,66% par rapport aux bornes inférieures déterminées par le modèle. Cependant, le modèle mathématique ne parvient pas à trouver aucune solution pour les instances de données réelles. Pour pouvoir résoudre ce problème complexe, une grande attention a été portée à la performance de l'implantation des algorithmes proposés afin d'améliorer leur rapidité en termes de temps d'exécution. Le problème reste très compliqué, surtout lorsque nous considérons une grande partie du réseau routier sous-jacent avec des données de trafic très précises. Pour cela, nous avons utilisé différentes techniques pour optimiser l'effort de calcul afin de résoudre le problème en évaluant l'impact engendré sur la précision tout en évitant la perte de précieuses informations. Nous avons développé deux types d'agrégation de données couvrant deux niveaux d'information différents. Premièrement, nous avons manipulé la structure du réseau en réduisant sa taille, et deuxièmement en contrôlant le niveau d'agrégation temporel pour générer les données de trafic et pour déterminer la vitesse d'un véhicule à tout moment. Pour la structure du réseau, nous avons utilisé différentes techniques de réduction de graphe pour en réduire la taille. Nous avons étudié la valeur et le compromis de l'information spatiale. Les solutions générées en utilisant le graphe réduit sont analysées dans le Chapitre 3 pour évaluer la qualité et la perte d'information dû à la réduction. Cette analyse démontre également que la transformation classique du TD-SPVRP en un problème de tournées dépendant du temps (Time-dependant VRP - TD-VRP) équivalent résulte en un graphe plus grand qui nécessite un temps de traitement important ce qui a un impact sur la qualité de la solution. Notre développement montre que la résolution du TD-SPVRP nécessite en moyenne 1445 secondes tandis que la résolution du TD-VRP associé nécessite 41 181 secondes. Garder un haut niveau de précision et réussir à réduire la taille du graphe est possible. En particulier, deux procédures de réduction ont été développées, la réduction des nœuds et la réduction des arcs parallèles. Les deux techniques réduisent la taille du graphe. La réduction des nœuds conduit à une amélioration de 1,11%, la réduction des arcs parallèles donne un écart de 2,57% signifiant la présence d'une distorsion dans le graphe réduit. En ce qui concerne les informations sur le trafic, nous avons analysé les compromis entre une grande quantité de données très précises et un plus petit volume de données agrégées avec une perte potentielle d'information. Ceci est fait en analysant la précision des données agrégées sous différents modèles de détermination des temps de parcours. Ces approches sont présentées dans le Chapitre 4. Au niveau de la prévision des temps de parcours, il est important que chaque segment routier ait des observations de vitesse pour chaque intervalle de temps considéré, ce que nous appelons le niveau de couverture du réseau. Notre analyse indique qu'une couverture complète du réseau routier à tout moment de la journée est nécessaire pour atteindre un niveau de précision élevé. Le recours à une agrégation élevée (de grands intervalles de temps) permet de réduire la taille du problème et d'obtenir une meilleure couverture des données, mais au prix d'une perte d'information. Les modèles analysés, LTM (link travel mode) et FSM (flow speed model), partagent les mêmes performances lorsqu'on utilise un grand intervalle de temps (120, 300 et 600 secondes), donc un niveau d'agrégation plus élevé, avec un écart moyen absolu de 5,5% par rapport aux temps de parcours observés. Cependant, avec une courte période (1, 10, 30 et 60 secondes), FSM fonctionne mieux que LTM. Pour un intervalle d'une seconde, FSM donne un écart absolu moyen de 6,70%, tandis que LTM fournit un écart de 11,17%. Ce chapitre détermine ainsi sous quelles conditions les modèles d'estimation de temps de parcours fonctionnent bien et procurent des estimations fidèles des temps de parcours réalisés. Cette thèse est structurée de la manière suivante. À la suite d'une introduction générale dans laquelle nous présentons le cadre conceptuel de la thèse et son organisation, le Chapitre 1 présente une revue de la littérature pour les deux problèmes fondamentaux étudiés, le problème de plus court chemin (Shortest path problem - SPP) et le VRP et leurs variantes développées au cours des années. Le Chapitre 2 introduit une nouvelle variante du VRP, le TD-SPVRP. Le Chapitre 3 présente les différentes techniques développées pour réduire la taille du réseau en manipulant les informations spatiales du réseau routier. L'impact de ces réductions est évalué et analysé sur des instances réelles en utilisant plusieurs heuristiques. Le Chapitre 4 traite l'impact de l'agrégation des données temporelle et des modèles d'évaluation des temps de parcours. Le dernier chapitre constitue une conclusion et ouvre des perspectives de recherche relatives à nos travaux. / The vehicle routing problem (VRP), introduced more than 60 years ago, is at the core of transportation systems. With decades of development, the VRP is one of the most studied problems in the literature, with a very rich set of variants. Yet, primarily due to the lack of data, two critical assumptions make the VRP fail to adapt effectively to traffic and congestion. The first assumption considers that the travel speed is constant over time ; the second, that each pair of customers is connected by an arc, ignoring the underlying street network. Traffic congestion is one of the biggest challenges in transportation systems. As traffic directly affects transportation activities, the whole supply chain needs to adjust to this factor. The continuous growth of freight in recent years worsens the situation, and a renewed focus on mobility, environment, and city logistics has shed light on these issues. Recently, advances in communications and real-time data acquisition technologies have made it possible to collect vehicle data such as their location, acceleration, driving speed, deceleration, etc. With the availability of this data, one can question the way we define, model, and solve transportation problems. This allows us to overcome the two issues indicated before and integrate congestion information and the whole underlying street network. We start by considering the whole underlying street network, which means we have customer nodes and intermediate nodes that constitute the street network. Then, we model the travel time of each street during the day. By dividing the day into small intervals, up to a precision of a second, we consider precise traffic information. This results in a new problem called the time-dependent shortest path vehicle routing problem (TD-SPVRP), in which we combine the time-dependent shortest path problem (TD-SPP) and the time-dependent VRP (TD-VRP), creating a more general and very challenging problem. The TD-SPVRP is closer to what can be found in real-world conditions, and it constitutes the topic of Chapter 2, where we formulate it as a mixed-integer linear programming model and design a fast and efficient heuristic algorithm to solve this problem. We test it on instances generated from actual traffic data from the road network in Québec City, Canada. Results show that the heuristic provides high-quality solutions with an average gap of only 5.66%, while the mathematical model fails to find a solution for any real instance. To solve the challenging problem, we emphasize the importance of a high-performance implementation to improve the speed and the execution time of the algorithms. Still, the problem is huge especially when we work on a large area of the underlying street network alongside very precise traffic data. To this end, we use different techniques to optimize the computational effort to solve the problem while assessing the impact on the precision to avoid the loss of valuable information. Two types of data aggregation are developed, covering two different levels of information. First, we manipulated the structure of the network by reducing its size, and second by controlling the time aggregation level to generate the traffic data, thus the data used to determine the speed of a vehicle at any time. For the network structure, we used different reduction techniques of the road graph to reduce its size. We studied the value and the trade-off of spatial information. Solutions generated using the reduced graph are analyzed in Chapter 3 to evaluate the quality and the loss of information from the reduction. We show that the transformation of the TD-SPVRP into an equivalent TD-VRP results in a large graph that requires significant preprocessing time, which impacts the solution quality. Our development shows that solving the TD-SPVRP is about 40 times faster than solving the related TD-VRP. Keeping a high level of precision and successfully reducing the size of the graph is possible. In particular, we develop two reduction procedures, node reduction and parallel arc reduction. Both techniques reduce the size of the graph, with different results. While the node reduction leads to improved reduction in the gap of 1.11%, the parallel arc reduction gives a gap of 2.57% indicating a distortion in the reduced graph. We analyzed the compromises regarding the traffic information, between a massive amount of very precise data or a smaller volume of aggregated data with some potential information loss. This is done while analyzing the precision of the aggregated data under different travel time models, and these developments appear in Chapter 4. Our analysis indicates that a full coverage of the street network at any time of the day is required to achieve a high level of coverage. Using high aggregation will result in a smaller problem with better data coverage but at the cost of a loss of information. We analyzed two travel time estimation models, the link travel model (LTM) and the flow speed model (FSM). They both shared the same performance when working with large intervals of time (120, 300, and 600 seconds), thus a higher level of aggregation, with an absolute average gap of 5.5% to the observed route travel time. With short periods (1, 10, 30, and 60 seconds), FSM performs better than LTM. For 1 second interval, FSM gives an average absolute gap of 6.70%, while LTM provides a gap of 11.17%. This thesis is structured as follows. After a general introduction in which we present the conceptual framework of the thesis and its organization, Chapter 1 presents the literature review for the two main problems of our development, the shortest path problem (SPP) and the VRP, and their time-dependent variants developed over the years. Chapter 2 introduces a new VRP variant, the TD-SPVRP. Chapter 3 presents the different techniques developed to reduce the size of the network by manipulating spatial information of the road network. The impact of these reductions is evaluated and analyzed on real data instances using multiple heuristics. Chapter 4 covers the impact of time aggregation data and travel time models when computing travel times on the precision of their estimations against observed travel times. The conclusion follows in the last chapter and presents some research perspectives for our works.

« Thèse présentée à l'École des gradués de l'Université Laval pour l'obtention du grade de philosophiæ doctor (Ph. D.) » / « Ayant mis en évidence les faiblesses analytiques de la dynamique des systèmes, notre recherche se préoccupera d'abord de modifier le modèle de dynamique des système pour pouvoir exploiter les outils puissants du Contrôle Automatique. Comme nous le verrons, cette modification consistera à procéder à une approximation linéaire du modèle initial de dynamique des systèmes qui est non linéaire. Dans cet effort, nous éviterons la méthode de transformation utilisée par les tenants du Contrôle Automatique (Appiah et Coyle 1983, Mohpatra et Sharma 1983) ; elle nous éloigne de ce qui est le langage par excellence de la dynamique des systèmes: DYNAMO; et surtout, elle est impuissante devant les modèles de grande taille. Nous partirons des principes de linéarisation, pour y procéder directement avec DYNAMO (on y arriverait avec n'importe quelle version de DYNAMO) sans recourir comme N. B. Forrester à un logiciel supplémentaire, DYNASTAT ou autre. Après avoir mis au point un instrument de linéarisation, la thèse montrera comment les gestionnaires peuvent recourir à l'analyse modale pour comprendre la nature et l'ampleur des forces dynamiques présentes au sein de leur entreprise. Pour cela, elle s'appuyera sur la correspondance existant entre la stabilité intrinsèque d'un système et les valeurs propres de son modèle linéaire. En troisième lieu, la thèse fournira une procédure de modification des forces dynamiques pour stabiliser et ajuster les divers secteurs de l'entreprise. La stabilisation consiste à identifier et changer les politiques qui causent l'instabilité. L'ajustement n'intervient qu'après la stabilisation; il consiste à identifier et à renforcer les politiques qui augmentent la stabilité. Basée sur les valeurs propres et l'analyse de leur sensibilité, cette procédure se révélera être un excellent moyen de mettre en évidence les effets réels des politiques suivies dans l'entreprise et d'évaluer l'opportunité de renforcer, atténuer ou éliminer ces politiques par des mesures appropriées. Enfin, elle donne une méthode d'implantation, dans le réel, des suggestions issues de l'analyse modale. L'application sera faite sur le modèle bien connu de Lyneis. Cela permettra d'identifier les sous-systèmes constitutifs du modèle global: leur nature, leur taille et leur mode d'interaction. Le degré d'intégration des différents secteurs de l'entreprise telle que modélisée par Lyneis apparaîtra avec plus de netteté. Nous nous servirons de la procédure développée dans cette thèse pour dégager les mesures et transformations nécessaires à la stabilisation accrue de chaque secteur. Il en résultera une meilleure performance. »--Pages 10-12

Ce mémoire porte sur la modélisation et l'analyse de réseaux de Petri de type Graphes d' Événements (GE) temporises et temporels, au moyen d'outils algébriques utilisée dans l'algèbre conventionnelle. La modélisation mathématique de ces systèmes dynamiques a événements discrets (SDED) conduit a une écriture polyédrale de la forme A:x b, o u x est un vecteur de dates. Nous donnons une technique algébrique permettant d'exprimer les trajectoires au plus tôt et réalisons une synthèse de la commande sous le critère classique de juste- a-temps d'un GE temporise. On utilise les concepts d'ordre composante par composante, de demi-treillis et d'inégalités monotones. Nous analysons la performance d'un graphe d'événements p-temporels, cette analyse se réduit a un problème de la programmation linéaire dont l'objectif est de calculer la valeur maximale et minimale du temps de cycle d'un graphe d'événements P-temporels. Dans une autre partie, nous constituons un modèle entrées/sorties dont le fonctionnement est proche de celui de l'équation d'état de l'automatique classique. Ensuite, en appliquant une formulation de la programmation linéaire, on calcule la trajectoire au plus tôt et au plus tard en utilisant une fonction objectif. Enfin, nous considérons le problème de la poursuite de trajectoire sur un horizon glissant.

Cette thèse s’inscrit dans le domaine de la programmation mathématique appliquée à la séparation d’aéronefs stabilisés en altitude. L’objectif est le développement d’algorithmes de résolution de conflits aériens ; l’enjeu étant d’augmenter la capacité de l’espace aérien afin de diminuer les retards et d’autoriser un plus grand nombre d’aéronefs à suivre leur trajectoire optimale. En outre, du fait de l’imprécision des prédictions relatives à la météo ou à l’état des aéronefs, l’incertitude sur les données est une caractéristique importante du problème. La démarche suivie dans ce mémoire s’attache d’abord au problème déterministe dont l’étude est nettement plus simple. Pour cela, quatre modèles basés sur la programmation non linéaire et sur la programmation linéaire à variables mixtes sont développés en intégrant notamment un critère reflétant la consommation de carburant et la durée de vol. Leur comparaison sur un ensemble de scénarios de test met en évidence l’intérêt d’utiliser un modèle linéaire approché pour l’étude du problème avec incertitudes. Un champ de vent aléatoire, corrélé en temps et en espace, ainsi qu’une erreur gaussienne sur la mesure de la vitesse sont ensuite pris en compte.Dans un premier temps, le problème déterministe est adapté en ajoutant une marge sur la norme de séparation grâce au calcul d’une approximation des probabilités de conflits. Finalement, une formulation stochastique avec recours est développée. Ainsi, les erreurs aléatoires sont explicitement incluses dans le modèle afin de tenir compte de la possibilité d’ordonner des manoeuvres de recours lorsque les erreurs observées engendrent de nouveaux conflits. / This thesis belongs to the field of mathematical programming, applied to the separation of aircraft stabilised on the same altitude. The primary objective is to develop algorithms for the resolution of air conflicts. The expected benefit of such algorithm is to increase the capacity of the airspace in order to reduce the number of late flights and let more aircraft follow their optimal trajectory. Moreover, meteorological forecast and trajectory predictions being inexact,the uncertainty on the data is an important issue. The approach that is followed focuses on the deterministic problem in the first place because it is much simpler. To do this, four nonlinear and mixed integer linear programming models, including a criterion based on fuel consumption and flight duration, are developed. Their comparison on a benchmark of scenarios shows the relevance of using an approximate linear model for the study of the problem with uncertainties.A random wind field, correlated in space and time, as well as speed measures with Gaussianerrors are then taken into account. As a first step, the deterministic problem is adapted by computinga margin from an approximate calculation of conflict probabilities and by adding it tothe reference separation distance. Finally, a stochastic formulation with recourse is developed.In this model, the random errors are explicitly included in order to consider the possibility of ordering recourse actions if the observed errors cause new conflicts.

Calculer une représentation 3D d'une scène rigide à partir d'une collection d'images est aujourd'hui possible grâce aux progrès réalisés par les méthodes de stéréo-vision multi-vues, et ce avec un simple appareil photographique. Le principe de reconstruction, découlant de travaux de photogrammétrie, consiste à recouper les informations provenant de plusieurs images, prises de points de vue différents, pour identifier les positions et orientations relatives de chaque cliché. Une fois les positions et orientations de caméras déterminées (calibration externe), la structure de la scène peut être reconstruite. Afin de résoudre le problème de calcul de la structure à partir du mouvement des caméras (Structure-from-Motion), des méthodes séquentielles et globales ont été proposées. Par nature, les méthodes séquentielles ont tendance à accumuler les erreurs. Cela donne lieu le plus souvent à des trajectoires de caméras qui dérivent et, lorsque les photos sont acquises autour d'un objet, à des reconstructions où les boucles ne se referment pas. Au contraire, les méthodes globales considèrent le réseau de caméras dans son ensemble. La configuration de caméras est recherchée et optimisée pour conserver au mieux l'ensemble des contraintes de cyclicité du réseau. Des reconstructions de meilleure qualité peuvent être obtenues, au détriment toutefois du temps de calcul. Cette thèse propose d'analyser des problèmes critiques au cœur de ces méthodes de calibration externe et de fournir des solutions pour améliorer leur performance (précision, robustesse, vitesse) et leur facilité d'utilisation (paramétrisation restreinte).Nous proposons tout d'abord un algorithme de suivi de points rapide et efficace. Nous montrons ensuite que l'utilisation généralisée de l'estimation robuste de modèles paramétriques a contrario permet de libérer l'utilisateur du réglage de seuils de détection, et d'obtenir une chaine de reconstruction qui s'adapte automatiquement aux données. Puis dans un second temps, nous utilisons ces estimations robustes adaptatives et une formulation du problème qui permet des optimisations convexes pour construire une chaine de calibration globale capable de passer à l'échelle. Nos expériences démontrent que les estimations identifiées a contrario améliorent de manière notable la qualité d'estimation de la position et de l'orientation des clichés, tout en étant automatiques et sans paramètres, et ce même sur des réseaux de caméras complexes. Nous proposons enfin d'améliorer le rendu visuel des reconstructions en proposant une optimisation convexe de la consistance colorée entre images / To compute a 3D representation of a rigid scene from a collection of pictures is now possible thanks to the progress made by the multiple-view stereovision methods, even with a simple camera. The reconstruction process, arising from photogrammetry, consists in integrating information from multiple images taken from different viewpoints in order to identify the relative positions and orientations. Once the positions and orientations (external calibration) of the cameras are retrieved, the structure of the scene can be reconstructed. To solve the problem of calculating the Structure from Motion (SfM), sequential and global methods have been proposed. By nature, sequential methods tend to accumulate errors. This is observable in trajectories of cameras that are subject to drift error. When pictures are acquired around an object it leads to reconstructions where the loops do not close. In contrast, global methods consider the network of cameras as a whole. The configuration of cameras is searched and optimized in order to preserve at best the constraints of the cyclical network. Reconstructions of better quality can be obtained, but at the expense of computation time. This thesis aims at analyzing critical issues at the heart of these methods of external calibration and at providing solutions to improve their performance(accuracy , robustness and speed) and their ease of use (restricted parametrization).We first propose a fast and efficient feature tracking algorithm. We then show that the widespread use of a contrario robust estimation of parametric models frees the user from choosing detection thresholds, and allows obtaining a reconstruction pipeline that automatically adapts to the data. Then in a second step, we use the adaptive robust estimation and a series of convex optimizations to build a scalable global calibration chain. Our experiments show that the a contrario based estimations improve significantly the quality of the pictures positions and orientations, while being automatic and without parameters, even on complex camera networks. Finally, we propose to improve the visual appearance of the reconstruction by providing a convex optimization to ensure the color consistency between images

Notre objectif est d’évaluer et de rendre opérationnelle la décomposition de problèmes d’optimisation sous contraintes. Nous nous sommes intéressés à deux problèmes en particulier : le problème de la recherche d’un plus grand sous-graphe commun (MCIS), et le problème de somme coloration minimale (MSCP). Il s’agit de problèmes NP-difficiles pour lesquels les approches de résolution complètes passent difficilement à l’échelle, et nous proposons de les améliorer à cet égard en décomposant ces problèmes en sous-problèmes indépendants. Les décompositions que nous proposons s’appuient sur la structure du problème initial pour créer des sous-problèmes de tailles équilibrées. Pour le MCIS, nous introduisons une décomposition basée sur la structure du graphe de compatibilité, et nous montrons que cette décomposition permet d’obtenir des sous-problèmes plus équilibrés que la méthode EPS classiquement utilisée pour paralléliser la résolution de problèmes en programmation par contraintes. Pour le MSCP, nous introduisons une nouvelle décomposition arborescente de hauteur bornée, et nous montrons comment tirer partie de la complémentarité de la programmation par contraintes et de la programmation linéaire en nombres entiers pour obtenir et résoudre les sous-problèmes indépendants qui en découlent. Nous proposons également une approche portfolio qui utilise des techniques d’apprentissage automatique pour choisir dynamiquement l’approche la plus performante en fonction du problème à résoudre. / The objective of this thesis is, from a general standpoint, to design and evaluate decomposition methods for solving constrained optimisation problems. Two optimisation problems in particular are considered: the maximum common induced subgraph problem, in which the largest common part between two graphs is to be found, and the sum colouring problem, where a graph must be coloured in a way that minimises a sum of weights induced by the employed colours. The maximum common subgraph (MCIS) problem is notably difficult, with a strong applicability in domains such as biology, chemistry and image processing, where the need to measure the similarity between structured objects represented by graphs may arise. The outstanding difficulty of this problem makes it strongly advisable to employ a decomposition method, possibly coupled with a parallelisation of the solution process. However, existing decomposition methods are not well suited to solve the MCIS problem: some lead to a poor balance between subproblems, while others, like tree decomposition, are downright inapplicable. To enable the structural decomposition of such problems, Chmeiss et al. proposed an approach, TR-decomposition, acting at a low level: the microstructure of the problem. This approach had yet to be applied to the MCIS problem. We evaluate it in this context, aiming at reducing the size of the search space while also enabling parallelisation. The second problem that caught our interest is the sum colouring problem. It is an NP-hard variant of the widely known classical graph colouring problem. As in most colouring problems, it basically consists in assigning colours to the vertices of a given graph while making sure no neighbour vertices use the same colour. In the sum colouring problem, however, each colour is associated with a weight. The objective is to minimise the sum of the weights of the colours used by every vertex. This leads to generally harder instances than the classical colouring problem, which simply requires to use as few colours as possible. Only a few exact methods have been proposed for this problem. Among them stand notably a constraint programming (CP) model, a branch and bound approach, as well as an integer linear programming (ILP) model. We led an in-depth investigation of CP's capabilities to solve the sum colouring problem, while also looking into ways to make it more efficient. Additionally, we evaluated a combination of integer linear programming and constraint programming, with the intention of conciliating the strong points of these highly complementary approaches. We took inspiration from the classical backtracking bounded by tree decomposition (BTD) approach. We employ a tree decomposition with a strictly bounded height. We then derive profit from the complementarity of our approaches by developing a portfolio approach, able to choose one of the considered approaches automatically by relying on a number of features extracted from each instance.

La conception d’un plan de transport d’un service ferroviaire est un processus qui se réalise entre deux ans et six mois avant la mise en service de celui-ci. Les principales phases de la conception sont la définition des dessertes, le calcul de la grille horaire et enfin l’organisation des roulements de rames et des conducteurs. La manière dont le plan de transport est conçu peut avoir de nombreuses conséquences sur la qualité de service : fréquence en gare insuffisante qui peut entrainer une perte de clients, robustesse de la grille horaire face à de petits incidents... En zone dense, tous ces éléments sont à prendre en compte, dès la conception de la grille horaire.Aujourd’hui, SNCF Transilien conçoit ses plans de transport en prenant d’abord en compte l’optimisation des ressources de production (sillons, rames et agents de conduite). Toutefois, l’augmentation des ressources mises en œuvre n’améliore plus l’adéquation du plan de transport à la demande des voyageurs. Ce mode de conception ne permet donc plus de faire face à l’augmentation de la demande de mobilité. C’est pourquoi il faut repenser la conception du plan de transport en intégrant immédiatement la dimension voyageuse.Nos travaux se concentrent sur les problématiques de conception de dessertes et de grille horaire, en prenant en compte le point de vue des voyageurs. Nous présentons un modèle multiobjectif de conception de dessertes, puis nous présentons un modèle de conception de grille horaire intégrant le choix d’itinéraire des voyageurs. Ensuite, nous présentons une méthode cherchant à intégrer ces deux modèles. Enfin, nous présentons une évaluation de nos résultats grâce à des indicateurs de fiabilité / The design of a railway transportation plan is a process achieved between two years and six months before it is put into service. The main phases in the design of a transportation plan are the line planning, the timetabling, the rolling stock and the crew scheduling.The design of the transportation plan can have many consequences on the quality of service: an inadequate frequency in station can cause a loss of passengers, sufficient number of seated places, robustness of the timetable in the face of small incidents... In dense area, as in the Ile-de-France region, all these elements must be taken into account as the transportation plan is designed.Today, SNCF Transilien designs its transportation plans by first taking into account the optimization of production resources (train paths, rolling stock units and drivers). However, today, the increase in resources implemented no longer improves the adequacy of the transportation plan to passengers’ demand. This design method no longer makes it possible to cope with the increase in the demand for mobility (+3% each year since 2000). This is why we must rethink the design of the transport plan by immediately integrating the passenger dimension. Our work focuses on issues of line planning and timetabling in a passenger-oriented approach. First, we present a multi-objective model for line planning. Then, we present a model of timetabling incorporating passenger route choice. Then, we initiate a method to integrate these two models. Finally, we present an evaluation of our results thanks to reliability indicators from the literature and a macroscopic simulation of the timetables

Le dimensionnement des lots de production est une des nombreuses activités survenant dans le cadre de la planification de production. Il a pour objet de déterminer quand et combien produire de façon à réaliser le meilleur compromis possible entre la minimisation des coûts liés à la production (coûts fixes de reconfiguration de la ressource, coûts de stockage...) et la satisfaction de la demande des clients Nous nous intéressons ici un problème de planification de production par lots connu sous le nom de "Discrete Lot-sizing and Scheduling Problem" ou "DLSP". Plus précisément, nous étudions plusieurs variantes de ce problème dans lesquelles les coûts et/ou les temps de changement de produits sur la ressource sont dépendant de la séquence et nous proposons diverses extensions d'une méthode disponible dans la littérature pour la résolution exacte du problème mono-niveau, mono-ressource. Nos contributions portent à la fois sur la modélisation du problème et sur l'implémentation de méthodes efficaces de résolution. En ce qui concerne la modélisation, nous étudions l'intégration de divers aspects opérationnels dans le modèle de base afin d'en améliorer la pertinence industrielle. Ainsi nous considérons les extensions suivantes : la prise en compte d'une structure de produits "multi-attributs" qui permet de diminuer la taille du problème d'optimisation à résoudre, l'intégration de temps de changement positifs afin de mieux modéliser la perte de production causée par une reconfiguration de la ressource et la présence de plusieurs ressources parallèles dont la production doit être planifiée simultanément. En ce qui concerne la résolution du problème, nous présentons pour chacune des extensions du modèle de base une approche de résolution visant à fournir des solutions optimales exactes. En général, les résultats de nos expériences numériques montrent l'utilité pratique de ces algorithmes pour la résolution d'instances de moyenne et grande taille en des temps de calcul compatibles avec une application industrielle