Search

Real-world problems involve several different criteria to take into account. For instance, a route may be associated with multiple features such as its cost, its ecological footprint, its duration, or its length. Resulting mathematical problems are addressed by multi-objective optimization. In general, there is no feasible solution able to maximize or minimize all objectives. Thus, decision makers want to examine the trade-off between the objectives in order to select the most suitable solution for them. Solving a multi-objective optimization problem consists of finding a set of points in the objective space, called non dominated points. No point in the objective space is better than a point of this set for all objectives. Few exact methods exist in literature to solve NP-hard multi- objective combinatorial problems, especially those with a NP-hard mono-objective variant. This thesis works on exact methods for such multi-objective problems, and the class of bi-objective vehicle routing problems is used as reference. The manuscript presents a column generation based-approach which aims to efficiently enumerate the set of non dominated points of the problems. We seek the best way to explore the objective space, and we propose different acceleration techniques based on structural properties. To show its generic aspect, the approach is applied to several bi-objective variants of the vehicle routing problem : the vehicle routing problem with time windows, the covering tour problem and the team-orienteering problem with time windows. Extensive computational experiments highlight the efficiency of the proposed method., De nombreux problèmes réels comportent plusieurs critères à considérer simultanément. À titre d’exemple, un trajet peut se caractériser par son coût, son impact écologique, son temps de parcours ou encore sa longueur. Les problèmes mathématiques résultants relèvent de l’optimisation multi-objectif. En général, il n’existe pas de solution réalisable optimisant tous les objectifs. Ainsi, les décideurs veulent analyser le compromis entre tous les objectifs pour pouvoir choisir la solution la plus adéquate. Par conséquent, résoudre un problème multi-objectif consiste à trouver un sous-ensemble de points, dits non dominés, dans l’espace des objectifs. Ces points sont associés à des solutions réalisables pour lesquelles il n’est pas possible d’améliorer un objectif sans en détériorer un autre. Peu de méthodes exactes existent dans la littérature pour traiter les problèmes combinatoires multi-objectif NP-difficiles, en particulier ceux dont la variante mono-objectif est déjà NP-difficile. Cette thèse s’inscrit dans l’étude des méthodes exactes pour de tels problèmes multi-objectif et utilise la classe des problèmes de tournées de véhicules bi-objectif comme référence. Les travaux se concentrent sur une approche basée sur la génération de colonnes et qui vise à énumérer efficacement l’ensemble des points non dominés de ces problèmes. Nous proposons notamment d’analyser diverses techniques d’exploration de l’espace des objectifs et de les améliorer grâce à des propriétés structurelles. Afin d’en démontrer la généricité, l’approche est appliquée à plusieurs variantes bi-objectif des problèmes de tournées de véhicules : le problème de tournées de véhicules avec fenêtre de temps, le problème de tournées couvrantes et le problème de course d’orientation par équipes avec fenêtre de temps. Les multiples tests numériques soulignent l’efficacité de la méthode proposée.

National audience; Real-world problems involve several different criteria to take into account. For instance, a route may be associated with multiple features such as its cost, its ecological footprint, its duration, or its length. Resulting mathematical problems are addressed by multi-objective optimization. In general, there is no feasible solution able to maximize or minimize all objectives. Thus, decision makers want to examine the trade-off between the objectives in order to select the most suitable solution for them. Solving a multi-objective optimization problem consists of finding a set of points in the objective space, called non dominated points. No point in the objective space is better than a point of this set for all objectives. Fewexact methods exist in literature to solve NP-hard multi-objective combinatorial problems, especially those with a NP-hard mono-objective variant.This thesis works on exact methods for such multi-objective problems, and the class of bi-objective vehicle routing problems is used as reference. The manuscript presents a column generation based-approach which aims to efficiently enumerate the set of non dominated points of the problems. We seek the best way to explore the objective space, and we propose different acceleration techniques based on structural properties. To show its generic aspect, the approach is applied to several bi-objective variants of the vehicle routing problem : the vehicle routing problem with time windows, the covering tour problem and the team-orienteering problem with time windows. Extensive computational experiments highlight the efficiency of the proposed method.; De nombreux problèmes réels comportent plusieurs critères à considérer simultanément.À titre d’exemple, un trajet peut se caractériser par son coût, son impact écologique, son temps de parcours ou encore sa longueur. Les problèmes mathématiques résultants relèvent de l’optimisation multi-objectif. En général, il n’existe pas de solution réalisable optimisant tous les objectifs. Ainsi, les décideurs veulent analyser le compromis entre tous les objectifs pour pouvoir choisir la solution la plus adéquate. Par conséquent, résoudre un problème multi-objectif consiste à trouver un sous-ensemble de points, dits non dominés, dans l’espace des objectifs. Ces points sont associés à des solutions réalisables pour lesquelles il n’est pas possible d’améliorer un objectif sans en détériorer un autre. Peu de méthodes exactes existent dans la littérature pour traiter les problèmes combinatoires multi-objectif NPdifficiles, en particulier ceux dont la variante mono-objectif est déjà NP-difficile.Cette thèse s’inscrit dans l’étude des méthodes exactes pour de tels problèmes multi-objectif et utilise la classe des problèmes de tournées de véhicules bi-objectif comme référence. Les travaux se concentrent sur une approche basée sur la génération de colonnes et qui vise à énumérer efficacement l’ensemble des points non dominés de ces problèmes.Nous proposons notamment d’analyser diverses techniques d’exploration de l’espace des objectifs et de les améliorer grâce à des propriétés structurelles. Afin d’en démontrer la généricité, l’approche est appliquée à plusieurs variantes bi-objectif des problèmes de tournées de véhicules : le problème de tournées de véhicules avec fenêtre de temps, le problème de tournées couvrantes (Covering Tour Problem) et le problème de course d’orientation par équipes avec fenêtre de temps (Team-Orienteering Problem with Time Windows). Les multiples tests numériques soulignent l’efficacité de la méthode proposée.

In present-day logistics, reducing negative impacts on society and on the environment is a difficult challenge for companies. In transportation, the main difficulty lies in the fact that most of the fleet used for inland shipping, is composed of conventional internal combustion vehicles. Thus, in order to reduce negative environmental impacts, nowadays electric vehicles are considered a suitable option to replace conventional vehicles in last mile operations. Although usage of electric vehicles comes with many benefits, it has some disadvantages that are restricting a massive adoption. Some of the disadvantages of electric vehicles are limited mileage range, low vehicle speed, relatively long charging times, limited payload, and lack of recharging facilities. This thesis is devoted to the joint location and routing decisions where the fleet is constituted of electrical vehicles. The location decisions concern where, when and how to recharge the vehicles while the routing optimization will decide which customers to serve and in which order. The main goal of this thesis is to continue the encouragement to the transition to EVs by proposing new strategies, and solution tools for transportation, namely routing problems, in a city logistics context. Additionally to promote the transition to EVs, the problems presented in this thesis aims to tackle two issues related to the usage of EVs, the impact of the idle times caused by recharging times and the issues related to availability of recharging infrastructure., Aujourd'hui, la réduction des impacts négatifs sur la société et sur l'environnement est un défi difficile pour les entreprises. La principale difficulté réside dans le fait que la majeure partie de la flotte utilisée est composée de véhicules à combustion interne. Afin de réduire les impacts négatifs sur l'environnement, les véhicules électriques sont aujourd'hui considérés comme une option appropriée pour remplacer les véhicules conventionnels dans les opérations du dernier kilomètre. Bien que l'utilisation de véhicules électriques présente de nombreux avantages, elle présente certains inconvénients qui limitent une adoption massive. Certains des inconvénients des véhicules électriques sont une autonomie limitée, une faible vitesse, des temps de charge relativement longs, une charge utile limitée et le manque d'installations de recharge. Cette thèse est consacrée aux décisions conjointes de localisation et de routage lorsque la flotte est constituée de véhicules électriques. L'objectif principal de cette thèse est de continuer à encourager la transition vers les VE en proposant de nouvelles stratégies et des outils de solution pour le transport, appelés les problèmes de transport dans un contexte logistique urbain. En plus de promouvoir la transition vers les VE, les problèmes présentés dans cette thèse visent à aborder deux questions liées à l'utilisation des VE, l'impact des temps d'inactivité causés par les temps de recharge et les questions liées à la disponibilité de l'infrastructure de rechargement.

National audience; The problem we study is inspired by an industrial collaboration between a third-party logistics, DHL Supply Chain, and a large French restaurant chain. As part of this partnership, DHL Supply Chain coordinates the actors of a domestic logistics network composed of suppliers, warehouses and restaurants. Over a certain time horizon, the restaurants issue requests of generic products (frozen products, beverages, etc.) that are manufactured by the suppliers. The mission of DHL Supply Chain is to ensure the supply of the restaurants. For that purpose, the company determines the shipping origin of each product ordered and designs a loading plan that characterizes the routes followed by the goods. DHL Supply Chain wants to develop innovative solutions to improve its competitiveness and optimize the profitability of its logistics operations. In this thesis, we present the Logistics Service Network Design Problem (LSNDP) which form! alizes the problematic of planning transportation operations in a supply chain. Our work aims to provide methodological solutions for solving industrial instances of the LSNDP. However, these industrial instances are too complex to be solved by generic operations research methods. We thus propose several algorithms that overcome the scaling of the parameters. In particular, we develop a graph reduction heuristic, as well as a dynamic Benders strategy that adapts to the increasing number of products. Through various computational studies, we evaluate the scalability of each algorithm with respect to the considered parameter. Finally, we combine these methods for the resolution of a real case.; La problématique que nous étudions est inspirée d’une collaboration industrielle entre un prestataire logistique, DHL Supply Chain, et une grande chaîne de restauration française. Dans le cadre de ce partenariat, DHL Supply Chain coordonne les acteurs d’un réseau logistique national composé de fournisseurs, d’entrepôts et de restaurants. Les restaurants émettent, sur un horizon temporel, des demandes de produits génériques (produits surgelés, boissons, etc.) fabriqués par les divers fournisseurs. La mission de DHL Supply Chain consiste à assurer l’approvisionnement des restaurants. Pour cela, l’entreprise détermine l’origine d’expédition de chaque produit commandé, et conçoit un plan de chargement caractérisant les itinéraires suivis par les marchandises. DHL Supply Chain souhaite développer des solutions innovantes afin d’améliorer sa compétitivité et d’optimiser la rentabilité de ses opérations logistiques. Dans cette thèse, ! nous présentons le Logistics Service Network Design Problem (LSNDP) qui formalise la problématique de planification des opérations de transport dans une chaîne d’approvisionnement. Nos travaux ont pour but d’apporter des solutions méthodologiques permettant la résolution d’instances industrielles du LSNDP. Or, ces instances industrielles sont trop complexes pour être résolues par des méthodes génériques de recherche opérationnelle. Nous proposons donc plusieurs algorithmes surmontant la mise à l’échelle des différents paramètres. Nous développons notamment une heuristique de réduction de graphe, ainsi qu’une stratégie de Benders dynamique adaptée à l’augmentation du nombre de produits. À travers diverses études expérimentales, nous évaluons la scalabilité de chaque algorithme par rapport au paramètre considéré. Enfin, nous hybridons ces méthodes pour la résolution d’un cas réel.

National audience; The problem we study is inspired by an industrial collaboration between a third-party logistics, DHL Supply Chain, and a large French restaurant chain. As part of this partnership, DHL Supply Chain coordinates the actors of a domestic logistics network composed of suppliers, warehouses and restaurants. Over a certain time horizon, the restaurants issue requests of generic products (frozen products, beverages, etc.) that are manufactured by the suppliers. The mission of DHL Supply Chain is to ensure the supply of the restaurants. For that purpose, the company determines the shipping origin of each product ordered and designs a loading plan that characterizes the routes followed by the goods. DHL Supply Chain wants to develop innovative solutions to improve its competitiveness and optimize the profitability of its logistics operations. In this thesis, we present the Logistics Service Network Design Problem (LSNDP) which formalizes the problematic of planning transportation operations in a supply chain. Our work aims to provide methodological solutions for solving industrial instances of the LSNDP. However, these industrial instances are too complex to be solved by generic operations research methods. We thus propose several algorithms that overcome the scaling of the parameters. In particular, we develop a graph reduction heuristic, as well as a dynamic Benders strategy that adapts to the increasing number of products. Through various computational studies, we evaluate the scalability of each algorithm with respect to the considered parameter. Finally, we combine these methods for the resolution of a real case.; La problématique que nous étudions est inspirée d’une collaboration industrielle entre un prestataire logistique, DHL Supply Chain, et une grande chaîne de restauration française. Dans le cadre de ce partenariat, DHL Supply Chain coordonne les acteurs d’un réseau logistique national composé de fournisseurs, d’entrepôts et de restaurants. Les restaurants émettent, sur un horizon temporel, des demandes de produits génériques (produits surgelés, boissons, etc.) fabriqués par les divers fournisseurs. La mission de DHL Supply Chain consiste à assurer l’approvisionnement des restaurants. Pour cela, l’entreprise détermine l’origine d’expédition de chaque produit commandé, et conçoit un plan de chargement caractérisant les itinéraires suivis par les marchandises. DHL Supply Chain souhaite développer des solutions innovantes afin d’améliorer sa compétitivité et d’optimiser la rentabilité de ses opérations logistiques. Dans cette th\`ese, nous présentons le Logistics Service Network Design Problem (LSNDP) qui formalise la problématique de plannification des opérations de transport dans une chaîne d’approvisionnement. Nos travaux ont pour but d’apporter des solutions méthodologiques permettant la résolution d’instances industrielles du LSNDP. Or, ces instances industrielles sont trop complexes pour être résolues par des méthodes génériques de recherche opérationnelle. Nous proposons donc plusieurs algorithmes surmontant la mise à l’échelle des différents param\`etres. Nous développons notamment une heuristique de réduction de graphe, ainsi qu’une stratégie de Benders dynamique adaptée à l’augmentation du nombre de produits. A travers diverses études expérimentales, nous évaluons la scalabilité de chaque algorithme par rapport au param\`etre considéré. Enfin, nous hybridons ces méthodes pour la résolution d’un cas réel.

Cloud Radio Access Network (C-RAN) has been proposed as a promising architecture to meet the exponential growth in data traffic demands and to overcome the challenges of next generation mobile networks (5G). The main concept of C-RAN is to decouple the BaseBand Units (BBU) and the Remote Radio Heads (RRH), and place the BBUs in common edge data centers (BBU pools) for centralized processing. This gives a number of benefits in terms of cost savings, network capacity improvement and resource utilization gains. However, network operators need to investigate scalable and cost-efficient algorithms for resource allocation problems to enable and facilitate the deployment of C-RAN architecture. Most of these problems are very complex and thus very hard to solve. Hence, we use combinatorial optimization which provides powerful tools to efficiently address these problems.One of the key issues in the deployment of C-RAN is finding the optimal assignment of RRHs (or antennas) to edge data centers (BBUs) when jointly optimizing the fronthaul latency and resource consumption. We model this problem by a mathematical formulation based on an Integer Linear Programming (ILP) approach to provide the optimal strategies for the RRH-BBU assignment problem and we propose also low-complexity heuristic algorithms to rapidly reach good solutions for large problem instances. The optimal RRH-BBU assignment reduces the expected latency and offers resource utilization gains. Such gains can only be achieved when reducing the inter-cell interference caused by the dense deployment of cell sites. We propose an exact mathematical formulation based on Branch-and-Cut methods that enables to consolidate and re-optimize the antennas radii in order to jointly minimize inter-cell interference and guarantee a full network coverage in C-RAN. In addition to the increase of inter-cell interference, the high density of cells in C-RAN increases the amount of baseband processing as well as the amount of data traffic demands between antennas and centralized data centers when strong latency requirements on fronthaul network should be met. Therefore, we discuss in the third part of this thesis how to determine the optimal placement of BBU functions when considering 3GPP split option to find optimal tradeoffs between benefits of centralization in C-RAN and transport requirements. We propose exact and heuristic algorithms based on combinatorial optimization techniques to rapidly provide optimal or near-optimal solutions even for large network sizes.; Cloud-Radio Access Network (C-RAN) est une architecture prometteuse pour faire face à l’augmentation exponentielle des demandes de trafic de données et surmonter les défis des réseaux de prochaine génération (5G). Le principe de base de CRAN consiste à diviser la station de base traditionnelle en deux entités : les unités de bande de base (BaseBand Unit, BBU) et les têtes radio distantes (Remote Radio Head, RRH) et à mettre en commun les BBUs de plusieurs stations dans des centres de données centralisés (pools de BBU). Ceci permet la réduction des coûts d’exploitation, l’amélioration de la capacité du réseau ainsi que des gains en termes d’utilisation des ressources. Pour atteindre ces objectifs, les opérateurs réseaux ont besoin d’investiguer de nouveaux algorithmes pour les problèmes d’allocation de ressources permettant ainsi de faciliter le déploiement de l’architecture C-RAN. La plupart de ces problèmes sont très complexes et donc très difficiles à résoudre. Par conséquent, nous utilisons l’optimisation combinatoire qui propose des outils puissants pour adresser ce type des problèmes.Un des principaux enjeux pour permettre le déploiement du C-RAN est de déterminer une affectation optimale des RRHs (antennes) aux centres de données centralisés (BBUs) en optimisant conjointement la latence sur le réseau de transmission fronthaul et la consommation des ressources. Nous modélisons ce problème à l’aide d’une formulation mathématique basée sur une approche de programmation linéaire en nombres entiers permettant de déterminer les stratégies optimales pour le problème d’affectation des ressources entre RRH-BBU et nous proposons également des heuristiques afin de pallier la difficulté au sens de la complexité algorithmique quand des instances larges du problème sont traitées, permettant ainsi le passage à l’échelle. Une affectation optimale des antennes aux BBUs réduit la latence de communication attendue et offre des gains en termes d’utilisation des ressources. Néanmoins, ces gains dépendent fortement de l’augmentation des niveaux d’interférence inter-cellulaire causés par la densité élevée des antennes déployées dans les réseaux C-RANs. Ainsi, nous proposons une formulation mathématique exacte basée sur les méthodes Branch-and-Cut qui consiste à consolider et ré-optimiser les rayons de couverture des antennes afin de minimiser les interférences inter-cellulaires et de garantir une couverture maximale du réseau conjointement. En plus de l’augmentation des niveaux d’interférence, la densité élevée des cellules dans le réseau CRAN augmente le nombre des fonctions BBUs ainsi que le trafic de données entre les antennes et les centres de données centralisés avec de fortes exigences en termes de latence sur le réseau fronthaul. Par conséquent, nous discutons dans la troisième partie de cette thèse comment placer d’une manière optimale les fonctions BBUs en considérant la solution split du 3GPP afin de trouver le meilleur compromis entre les avantages de la centralisation dans C-RAN et les forts besoins en latence et bande passante sur le réseau fronthaul. Nous proposons des algorithmes (exacts et heuristiques) issus de l’optimisation combinatoire afin de trouver rapidement des solutions optimales ou proches de l’optimum, même pour des instances larges du problèmes.

International audience; Par une méthode de sériation appliquéè a une matrice binaire, on essaye de retrouver l'ordre chro-nologique des Prêtres d'Hélios de l'île de Rhodes à la période hellénistique. La table binaire est celle de la correspondance entre ces magistrats changés chaque année et des fabricants de vin qui exportaient leur production dans des amphores marquées de leurs deux sceaux. L'optimisation d'un critère sur l'ensemble des ordres de 205 prêtres permet d'établir une chronologie compatible avec les données archéologiques connues.

Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimizationproblem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns.; Aujourd’hui, la conception de réseaux est une problématique cruciale qui se pose dans beaucoup de domaines tels que le transport ou l’énergie. En particulier, il est devenu nécessaire d’optimiser la façon dont sont conçus les réseaux permettant de produire de l’énergie. On se concentre ici sur la production électrique produite à travers des parcs éoliens. Cette énergie apparait plus que jamais comme une bonne alternative à la production d’électricité via des centrales thermiques ou nucléaires.Nous nous intéressons dans cette thèse à la conception du câblage collectant l’énergie dans les parcs éoliens. On connaît alors la position de l’ensemble des éoliennes appartenant au parc ainsi que celle du site central collecteur vers laquelle l’énergie doit être acheminée. On connaît également la position des câbles que l’on peut construire, leurs capacités, et la position des nœuds d’interconnexion possibles. Il s’agit de déterminer un câblage de coût minimal permettant de relier l’ensemble des éoliennes à la sous-station, tel que celui-ci soit résistant à un certain nombre de pannes sur le réseau.

High Performance Computing, which brings together all the players responsible for improving the computing performance of scientific applications on supercomputers, aims to achieve exaflopic performance. This race for performance is today characterized by the manufacture of heterogeneous machines in which each component is specialized. Among these components, system memories specialize too, and the trend is towards an architecture composed of several memories with complementary characteristics. The question arises then of these new machines use whose practical performance depends on the application data placement on the different memories. Compromising code update against performance is challenging. In this thesis, we have developed a data allocation on Heterogeneous Memory Architecture problem formulation. In this formulation, we have shown the benefit of a temporal analysis of the problem, because many studies were based solely on a spatial approach this result highlight their weakness. From this formulation, we developed an offline profiling tool to approximate the coefficients of the objective function in order to solve the allocation problem and optimize the allocation of data on a composite architecture composed of two main memories with complementary characteristics. In order to reduce the amount of code changes needed to execute an application according to our toolbox recommended allocation strategy, we have developed a tool that can automatically redirect data allocations from a minimum source code instrumentation. The performance gains obtained on mini-applications representative of the scientific applications coded by the community make it possible to assert that intelligent data allocation is necessary to fully benefit from heterogeneous memory resources. On some problem sizes, the gain between a naive data placement strategy, and an educated data allocation one, can reach up to ×3.75 speedup.; Le Calcul Haute Performance, regroupant l’ensemble des acteurs responsables de l’amélioration des performances de calcul des applications scientifiques sur supercalculateurs, s’est donné pour objectif d’atteindre des performances exaflopiques. Cette course à la performance se caractérise aujourd’hui par la fabrication de machines hétérogènes dans lesquelles chaque composant est spécialisé. Parmi ces composants, les mémoires du système se spécialisent, et la tendance va vers une architecture composée de plusieurs mémoires aux caractéristiques complémentaires. La question se pose alors de l’utilisation de ces nouvelles machines dont la performance pratique dépend du placement des données de l’application sur les différentes mémoires. Dans cette thèse, nous avons développé une formulation du problème d’allocation de donnée sur une Architecture à Mémoires Hétérogènes. Dans cette formulation, nous avons fait apparaître le bénéfice que pourrait apporter une analyse temporelle du problème, parce que de nombreux travaux reposaient uniquement sur une approche spatiale. À partir de cette formulation, nous avons développé un outil de profilage hors ligne pour approximer les coefficients de la fonction objective afin de résoudre le problème d’allocation et d’optimiser l’allocation des données sur une architecture composée deux de mémoires principales aux caractéristiques complémentaires. Afin de réduire la quantité de modifications nécessaires pour prendre en compte la stratégie d’allocation recommandée par notre boîte à outils, nous avons développé un outil capable de rediriger automatiquement les allocations de données à partir d’un minimum d’instrumentation dans le code source. Les gains de performances obtenus sur des mini-applications représentatives des applications scientifiques codées par la communauté permet d’affirmer qu’une allocation intelligente des données est nécessaire pour bénéficier pleinement de ressources mémoires hétérogènes. Sur certaines tailles de problèmes, le gain entre un placement naïf est une allocation instruite peut atteindre un facteur ×3.75.

High Performance Computing, which brings together all the players responsible for improving the computing performance of scientific applications on supercomputers, aims to achieve exaflopic performance. This race for performance is today characterized by the manufacture of heterogeneous machines in which each component is specialized. Among these components, system memories specialize too, and the trend is towards an architecture composed of several memories with complementary characteristics. The question arises then of these new machines use whose practical performance depends on the application data placement on the different memories. Compromising code update against performance is challenging. In this thesis, we have developed a data allocation on Heterogeneous Memory Architecture problem formulation. In this formulation, we have shown the benefit of a temporal analysis of the problem, because many studies were based solely on a spatial approach this result highlight their weakness. From this formulation, we developed an offline profiling tool to approximate the coefficients of the objective function in order to solve the allocation problem and optimize the allocation of data on a composite architecture composed of two main memories with complementary characteristics. In order to reduce the amount of code changes needed to execute an application according to our toolbox recommended allocation strategy, we have developed a tool that can automatically redirect data allocations from a minimum source code instrumentation. The performance gains obtained on mini-applications representative of the scientific applications coded by the community make it possible to assert that intelligent data allocation is necessary to fully benefit from heterogeneous memory resources. On some problem sizes, the gain between a naive data placement strategy, and an educated data allocation one, can reach up to ×3.75 speedup., Le Calcul Haute Performance, regroupant l’ensemble des acteurs responsables de l’amélioration des performances de calcul des applications scientifiques sur supercalculateurs, s’est donné pour objectif d’atteindre des performances exaflopiques. Cette course à la performance se caractérise aujourd’hui par la fabrication de machines hétérogènes dans lesquelles chaque composant est spécialisé. Parmi ces composants, les mémoires du système se spécialisent, et la tendance va vers une architecture composée de plusieurs mémoires aux caractéristiques complémentaires. La question se pose alors de l’utilisation de ces nouvelles machines dont la performance pratique dépend du placement des données de l’application sur les différentes mémoires. Dans cette thèse, nous avons développé une formulation du problème d’allocation de donnée sur une Architecture à Mémoires Hétérogènes. Dans cette formulation, nous avons fait apparaître le bénéfice que pourrait apporter une analyse temporelle du problème, parce que de nombreux travaux reposaient uniquement sur une approche spatiale. À partir de cette formulation, nous avons développé un outil de profilage hors ligne pour approximer les coefficients de la fonction objective afin de résoudre le problème d’allocation et d’optimiser l’allocation des données sur une architecture composée deux de mémoires principales aux caractéristiques complémentaires. Afin de réduire la quantité de modifications nécessaires pour prendre en compte la stratégie d’allocation recommandée par notre boîte à outils, nous avons développé un outil capable de rediriger automatiquement les allocations de données à partir d’un minimum d’instrumentation dans le code source. Les gains de performances obtenus sur des mini-applications représentatives des applications scientifiques codées par la communauté permet d’affirmer qu’une allocation intelligente des données est nécessaire pour bénéficier pleinement de ressources mémoires hétérogènes. Sur certaines tailles de problèmes, le gain entre un placement naïf est une allocation instruite peut atteindre un facteur ×3.75.

In the last decades, the use of renewable energy sources reduced the effect of global warming. Biomass is a promising energy resource to produce heat, electricity, and biofuel. An efficient supply chain design and optimal inventory management could contribute to reduce biofuel prices significantly and improve competitiveness with fossil fuel. This thesis addresses two crucial problems: biomass supply chain optimization and inventory control for a perishable product (biomass). The former is devoted to an issue of supplier selection and operation planning in biomass supply chains under uncertainty. This problem is formulated as a deterministic (MILP) model and a two-stage stochastic programming model. The deterministic model is solved by using a MIP solver GUROBI. An enhanced L-shaped decomposition method is developed to find an optimal solution for the stochastic model. The second deals with a stochastic inventory problem of a perishable product with uncertainty in both supply and demand. After demonstrating its optimal inventory policy is an order-to-level policy, a Lagrangian relaxation based algorithm is developed to quickly find a near-optimal solution of the problem. The stochastic inventory problem is, then, extended to a product with a fixed lifetime. The Conditional scenario method is developed to solve approximately this problem., Au cours des dernières décennies, l’utilisation de sources d’énergie renouvelables a réduit les effets du réchauffement climatique. La biomasse est une ressource énergétique prometteuse pour la production de la chaleur, de l’électricité et des biocarburants. Une conception efficace de la chaîne d’approvisionnement et une gestion optimale des stocks permettent à réduire significativement les prix des biocarburants et à améliorer la compétitivité contre des combustibles fossiles. Cette thèse aborde deux problèmes cruciaux : l’optimisation d’une chaîne logistique et la gestion des stocks périssables (biomasse). Le premier problème est consacré à la sélection des fournisseurs et la planification des opérations dans une chaîne logistique en biomasse. Ce problème est formulé sous forme de modèle déterministe (MILP) et de modèle stochastique à deux étapes. Le premier modèle est résolu de manière optimale par le solveur GUROBI. Une méthode de décomposition « L-shaped » est développée pour traiter le deuxième modèle. Le second problème consiste à la gestion des stocks d'un produit périssable sous incertitudes d’approvisionnement et de demande. Après avoir démontré que sa politique de gestion des stocks est une politique "order-up-to level", un algorithme basé sur la relaxation lagrangienne est développé pour trouver rapidement une solution quasi-optimale du problème. Ensuite, ce problème est étendu pour un produit à durée de vie fixe. La méthode « Conditional scenario » est développée pour résoudre approximativement ce problème.

Mixed fruit-vegetable cropping systems (MFVCS) are a promising way of ensuring environmentally sustainable agricultural production systems in response to the challenge of being able to fulfill local market requirements. They combine productions and make a better use of biodiversity. These agroforestry systems are based on a complex set of interactions modifying the utilization of light, water and nutrients. Thus, designing such systems requires to optimize the use of these resources : by maximizing positive interactions (facilitations) and minimizing negative ones (competitions). To reach these objectives, the system's design has to include the spatial and temporal dimensions, taking into account the evolution of above- and belowground interactions over a time horizon. For that, we define the MFVCAP using a discrete representation of the land and the interactions between vegetable crops and fruit trees. We formulate the problem as three models : binary quadratic program (BQP), mixed integer linear programming (MILP) and binary linear programming (01LP). We explore large models using exact solvers. The limits of exact methods in solving the MFVCS problem show the need for approximate methods, able to solve a large-scale system with solutions of good quality in reasonable time, which could be used in interactive design with farmers and advisers. We have implemented a C++ open-source solver, called baryonyx, which is a parallel version of a (generalized) Wedelin heuristic. We used a sensitivity analysis method to find useful continuous parameters. Once found, we fixed other parameters and let a genetic optimization algorithm using derivatives adjust the useful ones in order to get the best solutions for a given time limit. The optimized configuration could be used to solve larger instances of the same problem type. Baryonyx got competitive results compared to state-of-the-art exact and approximate solvers on crew and bus driver scheduling problems expressed as set partitioning problems. The results are less convincing on MFVCS but still able to produce valid solutions on large instances., Dans le cadre du développement durable et des innovations dans les systèmes agroalimentaires, les systèmes mixtes horticoles (vergers et maraîchage) visent à répondre aux enjeux actuels auxquels l'agriculture est confrontée, à savoir une diminution de la pollution des sols, une meilleure gestion des ressources (eau, énergies) et un enrichissement de la biodiversité, tout en continuant d'assurer des fonctions alimentaires. Ils combinent des productions à la fois diversifiées et relativement intensifiées, leur permettant de s'insérer en périphérie urbaine. Ces systèmes agroforestiers reposent sur un ensemble complexe d'interactions modifiant l'utilisation de la lumière, de l'eau et des nutriments. La conception d'un tel système doit donc optimiser l'utilisation de ces ressources en maximisant les interactions positives (facilitations) et en minimisant celles négatives (compétitions). Nous définissons le problème de verger-maraîcher comme un problème d'allocation des arbres et des cultures dans les dimensions spatio-temporelles. Nous proposons trois formulations mathématiques : modèle quadratique en variables binaires (BQP), modèle linéaire en variables mixtes (MILP) et modèle linéaire en variables binaires (01LP). Les limites des méthodes exactes pour résoudre ce problème sont présentées, montrant la nécessité d'appliquer des méthodes approchées, capables de résoudre des systèmes à grande échelle avec des solutions de bonne qualité en temps raisonnable. Pour cela, nous avons développé un solveur open source, baryonyx, qui est une version parallèle de l'heuristique de Wedelin (généralisée). Nous avons utilisé l'analyse de sensibilité pour identifier les paramètres les plus influents. Une fois trouvés, nous avons fixé les autres et utilisé un algorithme génétique pour régler les plus importants sur un ensemble d'instances d'entraînement. Le jeu de paramètres optimisé peut alors être utilisé pour résoudre d'autres instances de plus grande taille du même type de problème. baryonyx avec son réglage automatique obtient des résultats améliorant l'état-de-l'art sur des problèmes de partitionnement. Les résultats sont plus mitigés sur le problème de verger-maraîchage, bien que capable de passer à l'échelle.

Cloud Radio Access Network (C-RAN) has been proposed as a promising architecture to meet the exponential growth in data traffic demands and to overcome the challenges of next generation mobile networks (5G). The main concept of C-RAN is to decouple the BaseBand Units (BBU) and the Remote Radio Heads (RRH), and place the BBUs in common edge data centers (BBU pools) for centralized processing. This gives a number of benefits in terms of cost savings, network capacity improvement and resource utilization gains. However, network operators need to investigate scalable and cost-efficient algorithms for resource allocation problems to enable and facilitate the deployment of C-RAN architecture. Most of these problems are very complex and thus very hard to solve. Hence, we use combinatorial optimization which provides powerful tools to efficiently address these problems.One of the key issues in the deployment of C-RAN is finding the optimal assignment of RRHs (or antennas) to edge data centers (BBUs) when jointly optimizing the fronthaul latency and resource consumption. We model this problem by a mathematical formulation based on an Integer Linear Programming (ILP) approach to provide the optimal strategies for the RRH-BBU assignment problem and we propose also low-complexity heuristic algorithms to rapidly reach good solutions for large problem instances. The optimal RRH-BBU assignment reduces the expected latency and offers resource utilization gains. Such gains can only be achieved when reducing the inter-cell interference caused by the dense deployment of cell sites. We propose an exact mathematical formulation based on Branch-and-Cut methods that enables to consolidate and re-optimize the antennas radii in order to jointly minimize inter-cell interference and guarantee a full network coverage in C-RAN. In addition to the increase of inter-cell interference, the high density of cells in C-RAN increases the amount of baseband processing as well as the amount of data traffic demands between antennas and centralized data centers when strong latency requirements on fronthaul network should be met. Therefore, we discuss in the third part of this thesis how to determine the optimal placement of BBU functions when considering 3GPP split option to find optimal tradeoffs between benefits of centralization in C-RAN and transport requirements. We propose exact and heuristic algorithms based on combinatorial optimization techniques to rapidly provide optimal or near-optimal solutions even for large network sizes., Cloud-Radio Access Network (C-RAN) est une architecture prometteuse pour faire face à l’augmentation exponentielle des demandes de trafic de données et surmonter les défis des réseaux de prochaine génération (5G). Le principe de base de CRAN consiste à diviser la station de base traditionnelle en deux entités : les unités de bande de base (BaseBand Unit, BBU) et les têtes radio distantes (Remote Radio Head, RRH) et à mettre en commun les BBUs de plusieurs stations dans des centres de données centralisés (pools de BBU). Ceci permet la réduction des coûts d’exploitation, l’amélioration de la capacité du réseau ainsi que des gains en termes d’utilisation des ressources. Pour atteindre ces objectifs, les opérateurs réseaux ont besoin d’investiguer de nouveaux algorithmes pour les problèmes d’allocation de ressources permettant ainsi de faciliter le déploiement de l’architecture C-RAN. La plupart de ces problèmes sont très complexes et donc très difficiles à résoudre. Par conséquent, nous utilisons l’optimisation combinatoire qui propose des outils puissants pour adresser ce type des problèmes.Un des principaux enjeux pour permettre le déploiement du C-RAN est de déterminer une affectation optimale des RRHs (antennes) aux centres de données centralisés (BBUs) en optimisant conjointement la latence sur le réseau de transmission fronthaul et la consommation des ressources. Nous modélisons ce problème à l’aide d’une formulation mathématique basée sur une approche de programmation linéaire en nombres entiers permettant de déterminer les stratégies optimales pour le problème d’affectation des ressources entre RRH-BBU et nous proposons également des heuristiques afin de pallier la difficulté au sens de la complexité algorithmique quand des instances larges du problème sont traitées, permettant ainsi le passage à l’échelle. Une affectation optimale des antennes aux BBUs réduit la latence de communication attendue et offre des gains en termes d’utilisation des ressources. Néanmoins, ces gains dépendent fortement de l’augmentation des niveaux d’interférence inter-cellulaire causés par la densité élevée des antennes déployées dans les réseaux C-RANs. Ainsi, nous proposons une formulation mathématique exacte basée sur les méthodes Branch-and-Cut qui consiste à consolider et ré-optimiser les rayons de couverture des antennes afin de minimiser les interférences inter-cellulaires et de garantir une couverture maximale du réseau conjointement. En plus de l’augmentation des niveaux d’interférence, la densité élevée des cellules dans le réseau CRAN augmente le nombre des fonctions BBUs ainsi que le trafic de données entre les antennes et les centres de données centralisés avec de fortes exigences en termes de latence sur le réseau fronthaul. Par conséquent, nous discutons dans la troisième partie de cette thèse comment placer d’une manière optimale les fonctions BBUs en considérant la solution split du 3GPP afin de trouver le meilleur compromis entre les avantages de la centralisation dans C-RAN et les forts besoins en latence et bande passante sur le réseau fronthaul. Nous proposons des algorithmes (exacts et heuristiques) issus de l’optimisation combinatoire afin de trouver rapidement des solutions optimales ou proches de l’optimum, même pour des instances larges du problèmes.

The Stop Number Problem arises in the management of a dial-a-ride system with small autonomous electric vehicles. In such a system, a fleet of identical capacitated vehicles travels along a predefined circuit with fixed stations in order to serve clients requesting for a ride from an origin station to a destination station. Notice that multiple clients may share the same origin and/or destination stations. The Stop Number Problem consists of assigning each client request to avehicle such that no vehicle gets overloaded. The goal is to minimize the number of times the fleet of vehicles stops for picking up or delivering clients. When every client requests for exactly one seat in a vehicle, Stop Number Problem is called Unit Stop Number Problem. In this thesis, Unit Stop Number Problem is addressed as a combinatorial-optimization problem.First, we investigate the complexity of such problem. On the one hand, we study some properties of optimal solutions and derive a series of particular cases that are shown to be solvable in polynomial time. On the other hand, we show that Unit Stop Number Problem is NP-Hard even when restricted to case where each vehicle can take at most two clients at once and the graph induced by the client requests is planar bipartite. Such result -- which positively answers a conjecture known in the literature -- is then extended to other related problems such as the k-Edge Partitioning and the Traffic Grooming problem, improving their respective state-of-the-art complexity standards.In a second part, we consider an integer-programming formulation known in the literature for solving the Unit Stop Number Problem. A preliminary analysis is conducted in order to prove the weakness of such formulation. Afterwards, such formulation is reinforced through a polyhedral approach. We provide a facial study of the polytope associated with the solutions of this problem. New valid inequalities are introduced and necessary and sufficient conditions for which they are facet-defining are given.Finally, based on the discussed polyhedral results, we derive a new efficient branch-and-cut algorithm. Performance boosting features such as symmetry breaking methods and variable elimination/relaxation are also investigated and implemented into the developed framework. Results convincingly demonstrate the strength of the reinforcing valid inequalities and therefore of our branch-and-cut algorithm., Le Problème du Nombre d'Arrêts se présente dans la gestion d'un système de transport à la demande utilisant des véhicules électriques autonomes. Dans un tel système, une flotte de véhicules identiques parcourt un circuit prédéfini avec des stations fixes afin de desservir un ensemble de clients qui demandent un trajet entre une station d'origine et une station de destination. Notez que plusieurs clients peuvent partager les mêmes stations d'origine et/ou de destination. Le Problème du Nombre d'Arrêts consiste à affecter chaque demande à un véhicule de façon à ce qu'aucun véhicule ne soit surchargé. L'objectif est de minimiser le nombre d'arrêts effectués par la flotte de véhicules pour la collecte et la livraison des clients. Lorsque chaque client demande exactement une place dans un véhicule, le Problème du Nombre d'Arrêts est appelé Problème du Nombre d'Arrêts Unitaire. Dans cette thèse, le Problème du Nombre d'Arrêts Unitaire est traité comme un problème d'optimisation combinatoire.Tout d'abord, nous examinons la complexité du problème. D'une part, nous étudions certaines propriétés des solutions optimales et dérivons une série de cas particuliers dont la résolution peut être réalisée en temps polynomial. D'autre part, nous montrons que le Problème du Nombre d'Arrêts Unitaire est NP-Difficile même lorsqu'il est restreint au cas où chaque véhicule peut prendre au maximum deux clients à la fois et que le graphe induit par les demandes des clients est planaire bipartie. Ce résultat - qui répond positivement à une conjecture connue dans la littérature - est ensuite étendu à d'autres problèmes associés tels que le k-Edge Partitioning et le Traffic Grooming, améliorant ainsi leurs standards de complexité connus dans la littérature.Dans une deuxième partie, nous considérons une formulation de programmation linéaire en nombres entiers connue dans la littérature pour résoudre le Problème du Nombre d'Arrêts Unitaire. Une analyse préliminaire est effectuée afin de prouver la faiblesse de cette formulation. Par la suite, cette formulation est renforcée à l'aide d'une approche polyédrale. Nous fournissons une étude de faciale du polytope associée aux solutions de ce problème. De nouvelles inégalités valides sont introduites et les conditions nécessaires et suffisantes pour lesquelles elles définissent des facettes sont indiquées.Enfin, sur la base des résultats de l'approche polyédrale discutée, nous dérivons un nouvel algorithme de coupes et branchements efficace. Des fonctionnalités améliorant les performances de l’algorithme, telles que les méthodes de rupture de symétrie et l'élimination/relaxation des variables, sont également étudiées et mises en œuvre. Les résultats démontrent de manière convaincante la pertinence du renforcement des inégalités valides et donc de notre algorithme de coupes et branchements.

Our research work was motivated by a real problem of optimizing logistics transport at the Troyes Hospital Centre (CHT). The CHT is currently involved in the review and improvement of processes and the implementation of operational research techniques in order to provide solutions to the joint problems of product transport and driver scheduling. The objective of this study is to propose effective solutions to ensure the daily transport of food trolleys, linens, pharmaceuticals and warehouse products. After the problem was formalized, we proposed a three-phase resolution approach: the first deals with the known problem of collections and deliveries with a time window and a homogeneous fleet of vehicles, the second considers a heterogeneous fleet of vehicles, and the third phase integrates the assignment and sizing of the driver team. We have resulted in the development and implementation of a decision support tool. Following our work, we have developed and implemented in partnership with the start-up OPTA-LP, a software at the CHT. Throughout our work, we have developed accurate and approximate resolution methods, and also some techniques to reduce resolution time in an accurate resolution approach, or to improve a given solution in the case of an approximate method., Nos travaux de recherche ont été motivés par une problématique réelle d'optimisation du transport logistique du Centre Hospitalier de Troyes (CHT). Le CHT s'inscrit actuellement dans la revue et l'amélioration des processus et l'implémentation des techniques de recherche opérationnelle afin d’apporter des solutions aux problèmes conjoints de transports de produits et planification des chauffeurs. L'objectif de cette étude est de proposer des solutions efficaces afin d'assurer au quotidien le transport des chariots de repas, de linge, de produits pharmaceutiques et de produits magasiniers. Après la formalisation du problème, nous avons proposé une démarche de résolution composée de trois phases : la première traite du problème connu de collectes et livraisons avec fenêtre de temps et flotte homogène de véhicules, la seconde considère une flotte hétérogène de véhicules, et la troisième phase intègre l'affectation et le dimensionnement de l'équipe des chauffeurs. Nous avons abouti au développement et à la mise en place un outil d'aide à la décision. Nous avons suite à nos travaux, développé et mis en place en partenariat avec la start-up OPTA-LP un logiciel au CHT. Tout au long de nos travaux, nous avons développé des méthodes de résolution exactes et approchées, et aussi élaborer des techniques pour diminuer le temps de résolution dans une approche de résolution exacte, ou encore pour améliorer une solution donnée dans le cas d'une méthode approchée.

In this thesis, freight buses are introduced as a new public transportation means for city logistics. Like passenger buses, freight buses are standardized vehicles with fixed routes and time schedules. With stable and accurate services provided by freight buses, both shippers and customers can flexibly arrange their order delivery times. The route planning problem of freight buses for urban distribution is studied, where each freight bus repeatedly performs a tour that leaves from a distribution center, visits multiple depots, and returns to the center. This problem is a new variant of periodic vehicle routing problem, which was never studied in the literature. We have studied three variants of the freight bus routing planning problem: the basic freight bus routing problem with only deliveries, the freight bus routing problem with both pickups and deliveries, and the freight bus routing problem with stochastic demands. For each variant of the problem, after establishing its mathematical model, we have developed a metaheuristic algorithm to solve it. These metaheuristic algorithms include a memetic algorithm, an adaptive large neighborhood search algorithm, and an immune genetic algorithm combined with scenario-based optimization for cost evaluation. The choice of each algorithm considers the characteristics of the corresponding variant of the problem studied. The relevance of the mathematical models and the effectiveness of the proposed algorithms are proved by intensive numerical experiments., Dans cette thèse, les bus de fret sont introduits comme un nouveau moyen de transport collectif pour la logistique urbaine. Tout comme les autobus, les bus de fret sont des véhicules normalisés avec les itinéraires et les horaires fixes. Grace aux services stables et précis fournis par ces bus de fret, les expéditeurs et les consommateurs peuvent organiser de manière flexible les délais de livraison et de ramassage de leurs commandes. Le problème de planification d'itinéraires de bus de fret pour la distribution urbaine est étudié, où chaque bus de fret effectue répétitivement un circuit partant d'un centre de distribution, se rendant à plusieurs dépôts et retournant au centre. Ce problème est une nouvelle variante du problème de tournées périodiques de véhicules, qui n'a jamais été étudiée dans la littérature. Nous avons étudié trois variantes du problème de planification d’itinéraires de bus de fret : le problème de base avec demandes de livraison uniquement, le problème avec ramassages et livraisons, et le problème avec demandes de ramassage et de livraison stochastiques. Pour chaque variante du problème, après avoir établi un modèle mathématique, nous avons développé un algorithme métaheuristique pour la résoudre. Le choix de chaque algorithme prend en compte les caractéristiques de la variante correspondante du problème étudiée. La pertinence des modèles et l'efficacité des algorithmes proposés sont prouvées par des expérimentations numériques intensives.

As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, multi-objective evolutionary algorithms could greatly benefit from today's high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today.This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii) Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models., Comme ils requièrent généralement des capacités de calcul importantes pour explorer de grandes régions de l'espace de recherche dans la résolution de problèmes réels et complexes, les algorithmes évolutionnaires multi-objectifs peuvent bénéficier des nouvelles architectures de calcul haute performance. Ainsi, des approches parallèles ont été proposées à la fois pour réduire leur temps d'exécution et améliorer la qualité des solutions fournies. Bien que des progrès significatifs aient été réalisés ces dernières années dans la conception et l'amélioration de modèles parallèles pour les algorithmes évolutionnaires, la plupart de ces modèles ont une extensibilité limitée et des difficultés à manipuler des problèmes variés. Résoudre efficacement un problème combinatoire multi-objectifs sur une architecture de calcul haute performance demeure encore un défi aujourd'hui.Dans cette thèse, des mécanismes sont proposés au sein d'un nouveau modèle parallèle pour exploiter de multiples unités de calcul dans la résolution de problèmes multi-objectifs. L'approche générale reprend les principes des modèles en îles avec une division de l'espace objectif qui repose sur une méthode de regroupement. Les principales caractéristiques du modèle sont (i) la vue globale donnée à l'île organisatrice pour atteindre une meilleure distribution des solutions (ii) des communications asynchrones pour réduire les surcoûts du parallélisme (iii) des îles témoins pour accroitre la diversification (iv) une phase de recherche locale pour améliorer la qualité des solutions. Une étude expérimentale minutieuse est effectuée afin d'évaluer les performances de l'approche et plus particulièrement de chaque composante dans la résolution de deux problèmes combinatoires classiques, le problème de voyageur de commerce multi-objectifs et le problème d'affectation quadratique multi-objectifs. L'extensibilité et la qualité des solutions sont analysées comparativement aux modèles parallèles de la littérature.

Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimizationproblem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns., Aujourd’hui, la conception de réseaux est une problématique cruciale qui se pose dans beaucoup de domaines tels que le transport ou l’énergie. En particulier, il est devenu nécessaire d’optimiser la façon dont sont conçus les réseaux permettant de produire de l’énergie. On se concentre ici sur la production électrique produite à travers des parcs éoliens. Cette énergie apparait plus que jamais comme une bonne alternative à la production d’électricité via des centrales thermiques ou nucléaires.Nous nous intéressons dans cette thèse à la conception du câblage collectant l’énergie dans les parcs éoliens. On connaît alors la position de l’ensemble des éoliennes appartenant au parc ainsi que celle du site central collecteur vers laquelle l’énergie doit être acheminée. On connaît également la position des câbles que l’on peut construire, leurs capacités, et la position des nœuds d’interconnexion possibles. Il s’agit de déterminer un câblage de coût minimal permettant de relier l’ensemble des éoliennes à la sous-station, tel que celui-ci soit résistant à un certain nombre de pannes sur le réseau.

This thesis deals with people detection and re-identification in an environment instrumented by a network of disjoint-field cameras. It stands at the confluence of the Operational Research and Computer Vision communities as combinatorial optimization techniques are used to formalize new computer vision methods. In this context, a people visual detector, based on mixed-integer programming, is first propose that simultaneously take computation time and detection performances into account. This detector is evaluated and compared to the best detectors of the literature. These experiments, conducted on two public databases, clearly demonstrate the interest of our detector in terms of processing time with detection performance guarantee. The second part of the thesis deals with people re-identification. Our novel approach, called D-NCR (Directed Network Consistent Re-identification), explicitly takes minimum transit times in the camera network into account, as well as the network topology, in order to improve the re-identification performance. This problem is similar to the determination of particular maximum-profitable independent paths in an oriented graph. A mixed-integer program is proposed to model and solve this problem. The experiments made on a public dataset sound promising and tend to prove the potential of the approach., Cette thèse traite de la détection et de la ré-identification de personnes dans un environnement instrumenté par un réseau de caméras à champ disjoint. Elle est à la confluence des communautés Recherche Opérationnelle et Vision car elle s'appuie sur des techniques d'optimisation combinatoire pour formaliser de nouvelles modalités de vision par ordinateur. Dans ce contexte, un détecteur visuel de personnes, basé sur la programmation linéaire en nombres entiers, est tout d'abord proposé. Son originalité est de prendre en compte le coût de traitement et non uniquement les performances de détection. Ce détecteur est évalué et comparé aux détecteurs de la littérature les plus performants. Ces expérimentations menées sur deux bases de données publiques mettent clairement en évidence l'intérêt de notre détecteur en terme de coût de traitement avec garantie de performance de détection. La seconde partie de la thèse porte sur la modalité de ré-identification de personnes. L'originalité de notre approche, dénommée D-NCR (pour Directed Network Consistent Re-identification), est de prendre explicitement en compte les temps minimum de transit des personnes dans le réseau de caméras et sa topologie pour améliorer la performance de la ré-identification. On montre que ce problème s'apparente à une recherche de chemins disjoints particuliers à profit maximum dans un graphe orienté. Un programme linéaire en nombres entiers est proposé pour sa modélisation et résolution. Les évaluations réalisées sur une base publique d'images sont prometteuses et montrent le potentiel de cette approche.

The project structure arises in many fields of industry and services. It consists in performing a set of activities that may be linked by precedence relations, and use resources whose capacity is limited. The objective is to minimize a criterion usually linked to the duration or the cost of the project. Most of project scheduling problems in the literature assume that the same time scale should be used to determine activity start and completion dates and check resource constraints at each time. However, although it is often required in practice to build a precise schedule specifying the execution range of each activity, the resource usage can be evaluated on an aggregated basis, like worker shifts. In this thesis, a new model that enables the integration of these two time scales is presented in order to define the periodically aggregated resource-constrained project scheduling problem (PARCPSP). This problem is studied within the framework of complexity theory and several structural properties are established, highlighting major differences with the standard resource-constrained project scheduling problem (RCPSP). These properties allow deriving exact formulations based on integer linear programming, whose linear relaxations are compared. Moreover, several heuristics, such as schedule generations schemes, or an approached method based on a multi time scale iterative process, are proposed. Experimental results show the interest of these different methods and point out the intractability of the problem., La structure de projet se retrouve dans de nombreux contextes de l'industrie et des services. Il s'agit de réaliser un ensemble d'activités pouvant être connectées par des liens logiques de séquence (antériorité), en faisant appel à des ressources disponibles en quantité limitée. L'objectif est la minimisation d'un critère généralement lié à la durée ou au coût du projet. La plupart des problèmes d'ordonnancement de projet dans la littérature considèrent une unité de temps commune pour la détermination des dates d'exécution des activités et pour l'évaluation instantanée du respect des capacités des ressources qu'elles utilisent. Or, s'il est souvent nécessaire en pratique d'obtenir un calendrier détaillé des plages d'exécution des activités, l'utilisation des ressources peut être évaluée sur un horizon plus agrégé, comme par exemple les quarts de travail des employés. Dans cette thèse, un nouveau modèle intégrant ces deux échelles de temps est présenté afin de définir le problème d'ordonnancement de projet avec agrégation périodique des contraintes de ressources (PARCPSP). Ce problème est étudié du point de vue de la théorie de la complexité et des propriétés structurelles sont établies, mettant notamment en évidence des différences majeures avec le problème classique d'ordonnancement de projet sous contraintes de ressources (RCPSP). De ces propriétés sont dérivées des formulations exactes basées sur la programmation linéaire en nombres entiers, comparées en termes de qualité de la relaxation linéaire. Par ailleurs, plusieurs heuristiques, telles que des algorithmes de liste, ou une méthode approchée basée sur une résolution itérative qui exploite différentes échelles de temps, sont proposées. Les résultats expérimentaux montrent l'intérêt de ces différentes méthodes et illustrent la difficulté du problème.

Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods.; Plusieurs problèmes d'ordonnancement cyclique ont été étudiés dans la littérature. Cependant, la plupart de ces travaux considèrent que les paramètres sont connus avec certitude et ne prennent pas en compte les différents aléas qui peuvent survenir. Par ailleurs, un ordonnancement optimal pour un problème déterministe peut très vite devenir le pire ordonnancement en présence d'incertitude. Parmi les incertitudes que nous pouvons rencontrer dans les problèmes d'ordonnancement, la variation des durées des tâches par rapport au valeurs estimées, pannes des machines, incorporation de nouvelles tâches qui ne sont pas considérées au départ, etc. Dans cette thèse, nous étudions des problèmes d'ordonnancement cyclique où les durées des tâches sont affectées par des incertitudes. Ces dernières sont décrites par un ensemble d'incertitude où les durées des tâches sont supposées appartenir à des intervalles et le nombre de déviations par rapport aux valeurs nominales est contrôlé par un paramètre appelé budget d'incertitude. Nous étudions deux problèmes en particulier. Le premier est le problème d'ordonnancement cyclique de base (BCSP). Nous formulons celui-ci comme un problème d'optimisation robuste bi-niveau et, à partir des propriétés de cette formulation, nous proposons différents algorithmes pour le résoudre. Le deuxième problème considéré est le problème du jobshop cyclique. De manière similaire au BSCP, nous proposons une formulation en termes de problème d'optimisation bi-niveau et, en exploitant les algorithmes développés pour le problème d'ordonnancement cyclique de base, nous développons un algorithme de Branch-and-Bound pour le résoudre. Afin d'évaluer l'efficacité de notre méthode nous l'avons comparé à des méthodes de décomposition qui existent dans la littérature pour ce type de problèmes. Enfin, nous avons étudié une version du problème du jobshop cyclique où les durées des tâches prennent des valeurs dans des intervalles d'une manière uniforme et dont l'objectif est de minimiser la valeur moyenne du temps de cycle. Pour résoudre ce problème nous avons adopté un algorithme de Branch-and-Bound où chaque sous-problème de l'arbre de recherche consiste à calculer le volume d'un polytope. Enfin, pour montrer l'efficacité de chacune de ses méthodes, des résultats numériques sont présentés.

National audience; Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by ("the" a effacer) uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods.; Plusieurs problèmes d’ordonnancement cyclique ont été étudiés dans la littérature. Cependant, la plupart de ces travaux considèrent que les paramètres sont connus avec certitude et ne prennent pas en compte les différents aléas qui peuvent survenir. Par ailleurs, un ordonnancement optimal pour un problème déterministe peut très vite devenir le pire ordonnancement en présence d’incertitude. Parmi les incertitudes que nous pouvons rencontrer dans les problèmes d’ordonnancement, la variation des durées des tâches par rapport au valeurs estimées, pannes des machines, incorporation de nouvelles tâches qui ne sont pas considérées au départ, etc. Dans cette thèse, nous étudions des problèmes d’ordonnancement cyclique où les durées des tâches sont affectées par des incertitudes. Ces dernières sont décrites par un ensemble d’incertitude où les durées des tâches sont supposées appartenir à des intervalles et le nombre de déviations par rapport aux valeurs nominales est contrôlé par un paramètre appelé budget d’incertitude. Nous étudions deux problèmes en particulier. Le premier est le problème d’ordonnancement cyclique de base (BCSP). Nous formulons celui-ci comme un problème d’optimisation robuste bi-niveau et, à partir des propriétés de cette formulation, nous proposons différents algorithmes pour le résoudre. Le deuxième problème considéré est le problème du jobshop cyclique. De manière similaire au BSCP, nous proposons une formulation en termes de problème d’optimisation bi-niveau et, en exploitant les algorithmes développés pour le problème d’ordonnancement cyclique de base, nous développons un algorithme de Branch-and-Bound pour le résoudre. Afin d’évaluer l’efficacité de notre méthode nous l’avons comparé à des méthodes de décomposition qui existent dans la littérature pour ce type de problèmes. Enfin, nous avons étudié une version du problème du jobshop cyclique où les durées des tâches prennent des valeurs dans des intervalles d’une manière uniforme et dont l’objectif est de minimiser la valeur moyenne du temps de cycle. Pour résoudre ce problème nous avons adopté un algorithme de Branch-and-Bound où chaque sous-problème de l’arbre de recherche consiste à calculer le volume d’un polytope. Enfin, pour montrer l’efficacité de chacune de ses méthodes, des résultats numériques sont présentés.

In a sequencing experiment, we can only ``read'' small fragments (called reads) of DNA due to physical limitations, whose location on the genome is unknown.De novo assembly aims to put them together to retrieve the full DNA sequence, like a jigsaw puzzle.The OLC approach computes pairwise Overlaps between reads to find their Layout, and then derive a Consensus sequence.The layout can be cast as an instance of the Seriation combinatorial problem, seeking to reorder a set of elements based on their pairwise similarity, such that similar elements are nearby.In a noiseless setting, a spectral method can solve Seriation efficiently.Still, it often fails on noisy, real DNA data.Notably, assembly is challenged by repeated genomic regions (called repeats) causing distant fragments to be similar.Most assembly engines follow hierarchical, greedy schemes, including modules dedicated to detect and disambiguate repeats while constructing the output sequence.We explore a simpler approach using Seriation to lay out all reads at once.Our first contribution is to show that the spectral method can be seamlessly integrated in an OLC framework, yielding competitive results compared to standard methods on real data.However, due to repeats, the method can only find fragmented assemblies (with a few large assembled fragments), i.e., it does not succeed to layout all the reads together at once.In our second contribution, we extend the spectral method using a multidimensional spectral embedding.It provides a unifying framework for seriation and circular seriation, a variant searching for a cyclic ordering of the data.This method significantly improves the robustness of the original algorithm on noisy data, and yields single-contig assembly of bacterial genomes.As a third contribution, we introduce the Robust Seriation framework, formalizing the task of seriation on corrupted data. We outline the relation between (robust) seriation and other combinatorial problems, particularly for stylized matrices modeling DNA sequencing data. We propose dedicated algorithms that experimentally improve robustness on synthetic and real data, although they turn out to be more sensitive than the method constituting our second contribution.In a fourth contribution, we introduce the problem of Seriation with Duplications, which is motivated by the application of assembling cancer genome from spatial conformation (Hi-C) data.We propose an alternated minimization algorithm that can utilize methods designed to solve Robust Seriation, and evaluate it on toy data.; Les technologies de séquençage d'ADN ne permettent de lire que de courts fragments, dont on ignore la position sur le génome.L'assemblage de novo vise à reconstituer une séquence d'ADN entière en mettant ces fragments bout-à-bout, tel un puzzle.Dans l'approche OLC (overlap-layout-consensus), on calcule le chevauchement entre fragments afin de les disposer en ordre (réarrangement), puis extraire une séquence consensus.Le réarrangement peut s'écrire comme un problème combinatoire de sériation, où l'on réordonne des éléments comparable entre eux, de sorte que deux éléments adjacents sont similaires.Ce problème est résolu efficacement par un algorithme spectral en l'absence de bruit, mais il en va autrement des données génomiques réelles.En particulier, des régions du génome sont similaires bien qu'éloignées (séquences répétées), rendant l'assemblage problématique.Les méthodes d'assemblage emploient des algorithmes hiérarchiques et gloutons pour désambiguïser les séquences répétées.Nous proposons ici une approche épurée où l'on réarrange tous les fragments "d'un coup" via la résolution de sériation.Notre première contribution montre que l'emploi de la méthode spectrale pour le réarrangement s'intègre parfaitement dans le schéma OLC, produisant des résultats de qualité semblable aux méthodes standard.Cependant, du fait des séquences répétées, cette méthode produit des assemblages fragmentés (typiquement en quelques sous-séquences au lieu d'une).La deuxième contribution est un prolongement de la méthode spectrale lié à la réduction de dimension sous conservation de distances,englobant les problèmes de sériation et de sériation circulaire (une variante où les éléments peuvent être ordonnés selon un cycle) dans un cadre unifié.Ce prolongement rend l'algorithme robuste au bruit et résout le problème de fragmentation de l'assemblage précédent.Notre troisième contribution formalise la sériation robuste, où l'on souhaite réordonner des données bruitées. Nous décrivons des liens avec d'autres problèmes combinatoires, en particulier pour des matrices modélisant les données réelles d'ADN. Nous proposons des algorithmes adaptés, améliorant expérimentalement la robustesse sur données synthétiques et réelles, bien que moins clairement que la deuxième contribution.La quatrième contribution présente le problème de sériation avec duplication, motivé par l'assemblage de génomes cancéreux via des données de conformation spatiale, que nous tentons de résoudre avec un algorithme de projections alternées fondé en partie sur les méthodes de sériation robuste, sur données synthétiques.

In a sequencing experiment, we can only “read” small fragments (reads) of DNA due to physical limitations, whose location on the genome is unknown. De novo assembly aims to put them together to retrieve the full DNA sequence, like a jigsaw puzzle. The OLC approach computes pairwise Overlaps between reads to find their Layout, and then derive a Consensus sequence. The layout can be cast as an instance of the Seriation combinatorial problem, seeking to reorder a set of elements based on their pairwise similarity, such that similar elements are nearby. In a noiseless setting, a spectral method can solve Seriation efficiently. Still, it often fails on noisy, real DNA data. Notably, assembly is challenged by repeated genomic regions (repeats) causing distant fragments to be similar. Most assembly engines follow hierarchical, greedy schemes, including modules dedicated to detect and disambiguate repeats while constructing the output sequence. We explore a simpler approach using Seriation to lay out all reads at once. Our first contribution is to show that the spectral method can be seamlessly integrated in an OLC framework, yielding competitive results compared to standard methods on real data. However, due to repeats, the method can only find fragmented assemblies (with a few large assembled fragments), i.e., it does not succeed to lay- out all the reads together at once. In our second contribution, we extend the spectral method using a multidimensional spectral embedding. It provides a unifying framework for seriation and circular seriation, a variant searching for a cyclic ordering of the data. This method significantly improves the robustness of the original algorithm on noisy data, and yields single contig assembly of bacterial genomes. As a third contribution, we introduce the Robust Seriation framework, formalizing the task of seriation on corrupted data. We outline the relation between (robust) seriation and other combinatorial problems, particularly for stylized matrices modeling DNA sequencing data. We pro- pose dedicated algorithms that experimentally improve robustness on synthetic and real data, although they turn out to be more sensitive than the method constituting our second contribution. In a fourth contribution, we introduce the problem of Seriation with Duplications, which is motivated by the application of assembling cancer genome from spatial conformation (Hi-C) data. We propose an alternated minimization algorithm that can utilize methods designed to solve Robust Seriation, and evaluate it on toy data., Les technologies de séquençage d’ADN ne permettent de lire que de courts fragments, dont on ignore la position sur le génome. L’assemblage de novo vise à reconstituer une séquence d’ADN entière en mettant ces fragments bout-à-bout, tel un puzzle. Dans l’approche OLC (overlap-layout-consensus), on calcule le chevauchement entre fragments afin de les disposer en ordre (réarrangement), puis extraire une séquence consensus. Le réarrangement peut s’écrire comme un problème combinatoire de sériation, où l’on réordonne des éléments comparables entre eux, de sorte que deux éléments adjacents sont similaires. Ce problème est résolu efficacement par un algorithme spectral en l’absence de bruit, mais il en va autrement des données génomiques réelles. En particulier, des régions du génome sont similaires bien qu’éloignées (séquences répétées), rendant l’assemblage problématique. Les méthodes d’assemblage emploient des algorithmes hiérarchiques et gloutons pour désambiguïser les séquences répétées. Nous proposons ici une approche épurée où l’on réarrange tous les fragments « d’un coup »via la résolution de sériation. Notre première contribution montre que l’emploi de la méthode spectrale pour le réarrangement s’intègre par- faitement dans le schéma OLC, produisant des résultats de qualité semblable aux méthodes standard. Ce- pendant, du fait des séquences répétées, cette méthode produit des assemblages fragmentés (typiquement en quelques sous-séquences au lieu d’une). La deuxième contribution est un prolongement de la méthode spectrale lié à la réduction de dimension sous conservation de distances, englobant les problèmes de sériation et de sériation circulaire (une variante où les éléments peuvent être ordonnés selon un cycle) dans un cadre unifié. Ce prolongement rend l’algorithme robuste au bruit et résout le problème de fragmentation de l’assemblage précédent. Notre troisième contribution formalise la sériation robuste, où l’on souhaite réordonner des données bruitées. Nous décrivons des liens avec d’autres problèmes combinatoires, en particulier pour des matrices modélisant les données réelles d’ADN. Nous proposons des al- gorithmes adaptés, améliorant expérimentalement la robustesse sur données synthétiques et réelles, bien que moins clairement que la deuxième contribution. La quatrième contribution présente le problème de sériation avec duplication, motivé par l’assemblage de génomes cancéreux via des données de conformation spa- tiale, que nous tentons de résoudre avec un algorithme de projections alternées fondé en partie sur les méthodes de sériation robuste, sur données synthétiques.

The Min-up/min-down Unit Commitment Problem (MUCP), is to find a minimum-cost production plan on a discrete time horizon for a set of units producing electric power. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up and down time constraints. We show that the MUCP is strongly NP-hard, thus highlighting that the dynamic coupling of demands by minimum up and down time constraints represents one major source of difficulty. To cope with this difficulty, we introduce interval up-set inequalities, a new class of valid inequalities for the MUCP polytope, generalizing both min-up and extended cover inequalities from the 0-1 knapsack polytope. Facet defining cases are characterized and a Branch & Cut algorithm is devised. To deal with the symmetries impairing the solution process, we define sub-symmetries, as symmetries arising from a solution subset. We focus on integer linear programs whose (sub-)symmetry groups are symmetric groups acting on sub-columns of solution matrices. We propose a general framework to handle sub-symmetries in such problems. On this basis, two symmetry-breaking techniques are introduced. The first technique is an orbitopal fixing algorithm for the full (sub-)orbitope. The second technique is based on sub-symmetry breaking inequalities. Experimental results on MUCP instances show that the proposed techniques outperform state-of-the-art techniques. Finally we compare various Dantzig-Wolfe structures for the MUCP. We show that good quality lower bounds can be obtained by dualization of time-coupling constraints. Branch & Price results show that interval up-set inequalities are useful in this context.; Le Min-up/min-down Unit Commitment Problem (MUCP) consiste à trouver un plan de production de coût minimum pour un ensemble d’unités de production électrique sur un intervalle de temps discrétisé. A chaque pas de temps, la production totale doit satisfaire la demande prévue. Chaque unité respecte des temps minimum de marche et d’arrêt. Nous montrons que le MUCP est fortement NP-difficile, mettant ainsi en valeur l’impact du couplage dynamique des contraintes de demande sur la difficulté du problème. Pour appréhender cette difficulté, nous introduisons les inégalités interval up-set, généralisant les contraintes de min-up et les extended cover du sac à dos. Les facettes sont caractérisées, et un Branch & Cut est implémenté. Afin de briser les symétries du problème, nous définissons les sous-symétries comme des symétries apparaissant dans des sous-ensembles de solution. Nous considérons des PLNE dont les groupes de sous-symétrie sont des groupes symétriques agissant sur certaines sous-colonnes des matrices solutions. Nous proposons un cadre générique pour gérer les sous-symétries apparaissant dans ce type de problèmes. Deux techniques pour briser les sous-symétries sont proposées : la première est un algorithme de fixing orbitopal pour le full sub-orbitope, la seconde est basée sur des inégalités. Les résultats expérimentaux montrent que les techniques proposées sont plus performantes que les techniques de la littérature. Enfin, nous comparons différentes structures de décomposition pour le MUCP. Des bornes de bonne qualité sont obtenues par dualisation des contraintes dynamiques. Notre Branch&Price&Cut montre que les interval up-set sont utiles dans ce contexte.

The Min-up/min-down Unit Commitment Problem (MUCP), is to find a minimum-cost production plan on a discrete time horizon for a set of units producing electric power. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up and down time constraints. We show that the MUCP is strongly NP-hard, thus highlighting that the dynamic coupling of demands by minimum up and down time constraints represents one major source of difficulty. To cope with this difficulty, we introduce interval up-set inequalities, a new class of valid inequalities for the MUCP polytope, generalizing both min-up and extended cover inequalities from the 0-1 knapsack polytope. Facet defining cases are characterized and a Branch & Cut algorithm is devised. To deal with the symmetries impairing the solution process, we define sub-symmetries, as symmetries arising from a solution subset. We focus on integer linear programs whose (sub-)symmetry groups are symmetric groups acting on sub-columns of solution matrices. We propose a general framework to handle sub-symmetries in such problems. On this basis, two symmetry-breaking techniques are introduced. The first technique is an orbitopal fixing algorithm for the full (sub-)orbitope. The second technique is based on sub-symmetry breaking inequalities. Experimental results on MUCP instances show that the proposed techniques outperform state-of-the-art techniques. Finally we compare various Dantzig-Wolfe structures for the MUCP. We show that good quality lower bounds can be obtained by dualization of time-coupling constraints. Branch & Price results show that interval up-set inequalities are useful in this context.; Le Min-up/min-down Unit Commitment Problem (MUCP) consiste à trouver un plan de production de coût minimum pour un ensemble d’unités de production électrique sur un intervalle de temps discrétisé. A chaque pas de temps, la production totale doit satisfaire la demande prévue. Chaque unité respecte des temps minimum de marche et d’arrêt. Nous montrons que le MUCP est fortement NP-difficile, mettant ainsi en valeur l’impact du couplage dynamique des contraintes de demande sur la difficulté du problème. Pour appréhender cette difficulté, nous introduisons les inégalités interval up-set, généralisant les contraintes de min-up et les extended cover du sac à dos. Les facettes sont caractérisées, et un Branch & Cut est implémenté. Afin de briser les symétries du problème, nous définissons les sous-symétries comme des symétries apparaissant dans des sous-ensembles de solution. Nous considérons des PLNE dont les groupes de sous-symétrie sont des groupes symétriques agissant sur certaines sous-colonnes des matrices solutions. Nous proposons un cadre générique pour gérer les sous-symétries apparaissant dans ce type de problèmes. Deux techniques pour briser les sous-symétries sont proposées : la première est un algorithme de fixing orbitopal pour le full sub-orbitope, la seconde est basée sur des inégalités. Les résultats expérimentaux montrent que les techniques proposées sont plus performantes que les techniques de la littérature. Enfin, nous comparons différentes structures de décomposition pour le MUCP. Des bornes de bonne qualité sont obtenues par dualisation des contraintes dynamiques. Notre Branch&Price&Cut montre que les interval up-set sont utiles dans ce contexte.

National audience

Large-scale optimisation problems are usually hard to solve optimally. Approximation algorithms such as metaheuristics, able to quickly find sub-optimal solutions, are often preferred. This thesis focuses on multi-objective local search (MOLS) algorithms, metaheuristics able to deal with the simultaneous optimisation of multiple criteria. As many algorithms, metaheuristics expose many parameters that significantly impact their performance. These parameters can be either predicted and set before the execution of the algorithm, or dynamically modified during the execution itself.While in the last decade many advances have been made on the automatic design of algorithms, the great majority of them only deal with single-objective algorithms and the optimisation of a single performance indicator such as the algorithm running time or the final solution quality. In this thesis, we investigate the relations between automatic algorithm design and multi-objective optimisation, with an application on MOLS algorithms.We first review possible MOLS strategies ans parameters and present a general, highly configurable, MOLS framework. We also propose MO-ParamILS, an automatic configurator specifically designed to deal with multiple performance indicators. Then, we conduct several studies on the automatic offline design of MOLS algorithms on multiple combinatorial bi-objective problems. Finally, we discuss two online extensions of classical algorithm configuration: first the integration of parameter control mechanisms, to benefit from having multiple configuration predictions; then the use of configuration schedules, to sequentially use multiple configurations.; Les problèmes d’optimisation à grande échelle sont généralement difficiles à résoudre de façon optimale. Des algorithmes d’approximation tels que les métaheuristiques, capables de trouver rapidement des solutions sous-optimales, sont souvent préférés. Cette thèse porte sur les algorithmes de recherche locale multi-objectif (MOLS), des métaheuristiques capables de traiter l’optimisation simultanée de plusieurs critères. Comme de nombreux algorithmes, les MOLS exposent de nombreux paramètres qui ont un impact important sur leurs performances. Ces paramètres peuvent être soit prédits et définis avant l’exécution de l’algorithme, soit ensuite modifiés dynamiquement.Alors que de nombreux progrès ont récemment été réalisés pour la conception automatique d’algorithmes, la grande majorité d’entre eux ne traitent que d’algorithmes mono-objectif et l’optimisation d’un unique indicateur de performance. Dans cette thèse, nous étudions les relations entre la conception automatique d’algorithmes et l’optimisation multi-objective.Nous passons d’abord en revue les stratégies MOLS possibles et présentons un framework MOLS général et hautement configurable. Nous proposons également MO-ParamILS, un configurateur automatique spécialement conçu pour gérer plusieurs indicateurs de performance. Nous menons ensuite plusieurs études sur la conception automatique de MOLS sur de multiples problèmes combinatoires bi-objectifs. Enfin, nous discutons deux extensions de la configuration d’algorithme classique : d’abord l’intégration des mécanismes de contrôle de paramètres, pour bénéficier de multiples prédictions de configuration; puis l’utilisation séquentielle de plusieurs configurations.

Combinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3.; L’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3.

Combinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3.; L’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3.

To solve discrete optimization problems of black box type, many stochastic algorithms such as evolutionary algorithms or metaheuristics exist and prove to be particularly effective according to the problem to be solved. Depending on the observed properties of the problem, choosing the most relevant algorithm is a difficult problem. In the original framework of parallel and distributed computing environments, we propose and analyze different adaptive optimization algorithm selection strategies. These selection strategies are based on reinforcement learning methods automatic, from the field of artificial intelligence, and on information sharing between computing nodes. We compare and analyze selection strategies in different situations. Two types of synchronous distributed computing environment are discussed : the island model and the master-slave model. On the set of nodes synchronously at each iteration, the adaptive selection strategy chooses an algorithm according to the state of the search for the solution. In the first part, two problems OneMax and NK, one unimodal and the other multimodal, are used as benchmarks for this work. Then, to better understand and improve the design of adaptive selection strategies, we propose a modeling of the optimization problem and its local search operator. In this modeling, an important characteristic is the average gain of an operator according to the fitness of the candidate solution. The model is used in the synchronous framework of the master-slave model. A selection strategy is broken down into three main components : the aggregation of the rewards exchanged, the learning scheme and the distribution of the algorithms on the computing nodes. In the final part, we study three scenarios, and we give keys to understanding the relevant use of adaptive selection strategies over naïve strategies. In the framework of the master-slave model, we study the different ways of aggregating the rewards on the master node, the distribution of the optimization algorithms of the nodes of computation and the time of communication. This thesis ends with perspectives in the field of distributed adaptive stochastic optimization.; Pour résoudre des problèmes d'optimisation discret de type boîte noire, de nombreux algorithmes stochastiques tels que les algorithmes évolutionnaires ou les métaheuristiques existent et se révèlent particulièrement efficaces selon le problème à résoudre. En fonction des propriétés observées du problème, choisir l'algorithme le plus pertinent est un problème difficile. Dans le cadre original des environnements de calcul parallèle et distribué, nous proposons et analysons différentes stratégies adaptative de sélection d'algorithme d'optimisation. Ces stratégies de sélection reposent sur des méthodes d'apprentissage automatique par renforcement, issu du domaine de l'intelligence artificielle, et sur un partage d'information entre les noeuds de calcul. Nous comparons et analysons les stratégies de sélection dans différentes situations. Deux types d'environnement de calcul distribué synchrone sont abordés : le modèle en île et le modèle maître-esclave. Sur l'ensemble des noeuds de manière synchrone à chaque itération la stratégie de sélection adaptative choisit un algorithme selon l'état de la recherche de la solution. Dans une première partie, deux problèmes OneMax et NK, l'un unimodal et l'autre multimodal, sont utilisés comme banc d'essai de ces travaux. Ensuite, pour mieux saisir et améliorer la conception des stratégies de sélection adaptatives, nous proposons une modélisation du problème d'optimisation et de son opérateur de recherche locale. Dans cette modélisation, une caractéristique importante est le gain moyen d'un opérateur en fonction de la fitness de la solution candidate. Le modèle est utilisé dans le cadre synchrone du modèle maître-esclave. Une stratégie de sélection se décompose en trois composantes principales : l'agrégation des récompenses échangées, la technique d'apprentissage et la répartition des algorithmes sur les noeuds de calcul. Dans une dernière partie, nous étudions trois scénarios et nous donnons des clés de compréhension sur l'utilisation pertinente des stratégies de sélection adaptative par rapport aux stratégies naïves. Dans le cadre du modèle maître-esclave, nous étudions les différentes façons d'agréger les récompenses sur le noeud maître, la répartition des algorithmes d'optimisation sur les noeuds de calcul et le temps de communication. Cette thèse se termine par des perspectives pour le domaine de l'optimisation stochastique adaptative distribuée.

To solve discrete optimization problems of black box type, many stochastic algorithms such as evolutionary algorithms or metaheuristics exist and prove to be particularly effective according to the problem to be solved. Depending on the observed properties of the problem, choosing the most relevant algorithm is a difficult problem. In the original framework of parallel and distributed computing environments, we propose and analyze different adaptive optimization algorithm selection strategies. These selection strategies are based on reinforcement learning methods automatic, from the field of artificial intelligence, and on information sharing between computing nodes. We compare and analyze selection strategies in different situations. Two types of synchronous distributed computing environment are discussed : the island model and the master-slave model. On the set of nodes synchronously at each iteration, the adaptive selection strategy chooses an algorithm according to the state of the search for the solution. In the first part, two problems OneMax and NK, one unimodal and the other multimodal, are used as benchmarks for this work. Then, to better understand and improve the design of adaptive selection strategies, we propose a modeling of the optimization problem and its local search operator. In this modeling, an important characteristic is the average gain of an operator according to the fitness of the candidate solution. The model is used in the synchronous framework of the master-slave model. A selection strategy is broken down into three main components : the aggregation of the rewards exchanged, the learning scheme and the distribution of the algorithms on the computing nodes. In the final part, we study three scenarios, and we give keys to understanding the relevant use of adaptive selection strategies over naïve strategies. In the framework of the master-slave model, we study the different ways of aggregating the rewards on the master node, the distribution of the optimization algorithms of the nodes of computation and the time of communication. This thesis ends with perspectives in the field of distributed adaptive stochastic optimization.; Pour résoudre des problèmes d'optimisation discret de type boîte noire, de nombreux algorithmes stochastiques tels que les algorithmes évolutionnaires ou les métaheuristiques existent et se révèlent particulièrement efficaces selon le problème à résoudre. En fonction des propriétés observées du problème, choisir l'algorithme le plus pertinent est un problème difficile. Dans le cadre original des environnements de calcul parallèle et distribué, nous proposons et analysons différentes stratégies adaptative de sélection d'algorithme d'optimisation. Ces stratégies de sélection reposent sur des méthodes d'apprentissage automatique par renforcement, issu du domaine de l'intelligence artificielle, et sur un partage d'information entre les noeuds de calcul. Nous comparons et analysons les stratégies de sélection dans différentes situations. Deux types d'environnement de calcul distribué synchrone sont abordés : le modèle en île et le modèle maître-esclave. Sur l'ensemble des noeuds de manière synchrone à chaque itération la stratégie de sélection adaptative choisit un algorithme selon l'état de la recherche de la solution. Dans une première partie, deux problèmes OneMax et NK, l'un unimodal et l'autre multimodal, sont utilisés comme banc d'essai de ces travaux. Ensuite, pour mieux saisir et améliorer la conception des stratégies de sélection adaptatives, nous proposons une modélisation du problème d'optimisation et de son opérateur de recherche locale. Dans cette modélisation, une caractéristique importante est le gain moyen d'un opérateur en fonction de la fitness de la solution candidate. Le modèle est utilisé dans le cadre synchrone du modèle maître-esclave. Une stratégie de sélection se décompose en trois composantes principales : l'agrégation des récompenses échangées, la technique d'apprentissage et la répartition des algorithmes sur les noeuds de calcul. Dans une dernière partie, nous étudions trois scénarios et nous donnons des clés de compréhension sur l'utilisation pertinente des stratégies de sélection adaptative par rapport aux stratégies naïves. Dans le cadre du modèle maître-esclave, nous étudions les différentes façons d'agréger les récompenses sur le noeud maître, la répartition des algorithmes d'optimisation sur les noeuds de calcul et le temps de communication. Cette thèse se termine par des perspectives pour le domaine de l'optimisation stochastique adaptative distribuée.

This thesis concerns the human resource planning by paying a special attention to the human aspect and ergonomic factors in the manufacturing domain. A number of mathematical models are presented to formulate the studied workforce scheduling and planning problems. In the planning models, the productivity of the manufacturing system and the well-being of the workers are targeted. In this way, a worker assignment approach is presented to reduce the production time and a job rotation scheduling approach is presented to balance the workloads on the operators. For this purpose, an ergonomic analysis is carried out on the jobs of the studied production system. This analysis results in the traffic light evaluation for the jobs, i.e., the jobs are categorized into the low, medium and high workload levels which are presented respectively by the green, yellow and red colors. A mathematical approach is developed to convert these outputs to the numerical values, because the quantitative parameters are more applicable for the optimization of the planning. A multi-objective programming is proposed to optimize two mentioned objectives of the studied workforce scheduling problem. Both linear aggregation and epsilon-constraint methods are applied to solve this optimization model. Furthermore, this thesis presents a novel variant of the assignment problem called sequencing generalized assignment problem which is defined for workforce scheduling in a combined system consisting of the jobs in series and in parallel. It is proved that this combinatorial optimization problem is NP-hard and the exact methods are not able to solve the large-scale instances. Hence, three approximate methods consisting of two matheuristic and a hybrid heuristic approaches are developed to solve it. The matheuristic methods are based on the decomposition of the formulation to break down and simplify the main model into two or more smaller models. The third method is a greedy heuristic combined with a local search. The efficiency of the three mentioned methods is evaluated by various instances of different sizes. Moreover, in the last step of this thesis, the human resource planning for a home healthcare system is formulated mathematically. According to the structure of the system, an integration of the worker assignment and vehicle routing problems is presented. Finally, a three-steps matheuristic approach is proposed to solve this combinatorial optimization problem.; Cette thèse porte sur la planification du personnel en accordant une attention particulière à l'aspect humain et aux facteurs ergonomiques dans le domaine de la production. Un certain nombre de modèles mathématiques sont présentés pour formuler les problèmes d'ordonnancement et de planification du personnel étudié. Concernant les modèles de planification, la productivité du système de fabrication et le bien-être des travailleurs sont ciblés. De cette manière, une méthode d'affectation des travailleurs est présentée pour réduire le temps de production et une méthode d'ordonnancement pour la rotation des tâches est présentée afin d’équilibrer la charge de travail des opérateurs. À cet effet, une analyse ergonomique est effectuée sur les postes de travail du système de production étudié. Cette analyse aboutit à l'évaluation des postes du travail suivant la convention dite des feux de circulation, c'est-à-dire que les postes sont classés dans les niveaux de charge faible, moyen et élevé qui sont représentés respectivement par les couleurs verte, jaune et rouge. Une approche mathématique est développée pour convertir ces résultats en valeurs numériques, car les paramètres quantitatifs sont plus applicables pour l'optimisation de la planification. Une programmation multi-objectifs est proposée pour optimiser les deux objectifs mentionnés du problème d'ordonnancement de tournée du personnel étudié. Les méthodes d'agrégation linéaire et de ε-contrainte sont appliquées pour résoudre ce modèle d'optimisation. En outre, cette thèse présente une nouvelle variante du problème d'affectation appelé problème d'affectation généralisée par séquence qui est défini pour la planification du personnel dans un système combiné constitué des postes de travail en série et en parallèle. Il est prouvé que ce problème d'optimisation combinatoire est NP-difficile et les méthodes exactes ne sont pas capables de résoudre les instances de grande taille. Ainsi, trois méthodes approchées composées de deux approches matheuristiques et une heuristique hybride sont développées pour résoudre ce problème. Les méthodes matheuristiques sont basées sur la décomposition de la formulation pour simplifier le modèle principal en deux ou plusieurs modèles plus petits. La troisième méthode est une heuristique gloutonne combinée à une recherche locale. En outre, dans la dernière étape de cette thèse, la planification des ressources humaines pour un système de soins à domicile est formulée mathématiquement. Selon la structure du système, une intégration des problèmes d'affectation et de tournées de véhicules est présentée. Enfin, une approche matheuristique en trois étapes est proposée pour résoudre ce problème d'optimisation combinatoire.

This thesis concerns the human resource planning by paying a special attention to the human aspect and ergonomic factors in the manufacturing domain. A number of mathematical models are presented to formulate the studied workforce scheduling and planning problems. In the planning models, the productivity of the manufacturing system and the well-being of the workers are targeted. In this way, a worker assignment approach is presented to reduce the production time and a job rotation scheduling approach is presented to balance the workloads on the operators. For this purpose, an ergonomic analysis is carried out on the jobs of the studied production system. This analysis results in the traffic light evaluation for the jobs, i.e., the jobs are categorized into the low, medium and high workload levels which are presented respectively by the green, yellow and red colors. A mathematical approach is developed to convert these outputs to the numerical values, because the quantitative parameters are more applicable for the optimization of the planning. A multi-objective programming is proposed to optimize two mentioned objectives of the studied workforce scheduling problem. Both linear aggregation and epsilon-constraint methods are applied to solve this optimization model. Furthermore, this thesis presents a novel variant of the assignment problem called sequencing generalized assignment problem which is defined for workforce scheduling in a combined system consisting of the jobs in series and in parallel. It is proved that this combinatorial optimization problem is NP-hard and the exact methods are not able to solve the large-scale instances. Hence, three approximate methods consisting of two matheuristic and a hybrid heuristic approaches are developed to solve it. The matheuristic methods are based on the decomposition of the formulation to break down and simplify the main model into two or more smaller models. The third method is a greedy heuristic combined with a local search. The efficiency of the three mentioned methods is evaluated by various instances of different sizes. Moreover, in the last step of this thesis, the human resource planning for a home healthcare system is formulated mathematically. According to the structure of the system, an integration of the worker assignment and vehicle routing problems is presented. Finally, a three-steps matheuristic approach is proposed to solve this combinatorial optimization problem.; Cette thèse porte sur la planification du personnel en accordant une attention particulière à l'aspect humain et aux facteurs ergonomiques dans le domaine de la production. Un certain nombre de modèles mathématiques sont présentés pour formuler les problèmes d'ordonnancement et de planification du personnel étudié. Concernant les modèles de planification, la productivité du système de fabrication et le bien-être des travailleurs sont ciblés. De cette manière, une méthode d'affectation des travailleurs est présentée pour réduire le temps de production et une méthode d'ordonnancement pour la rotation des tâches est présentée afin d’équilibrer la charge de travail des opérateurs. À cet effet, une analyse ergonomique est effectuée sur les postes de travail du système de production étudié. Cette analyse aboutit à l'évaluation des postes du travail suivant la convention dite des feux de circulation, c'est-à-dire que les postes sont classés dans les niveaux de charge faible, moyen et élevé qui sont représentés respectivement par les couleurs verte, jaune et rouge. Une approche mathématique est développée pour convertir ces résultats en valeurs numériques, car les paramètres quantitatifs sont plus applicables pour l'optimisation de la planification. Une programmation multi-objectifs est proposée pour optimiser les deux objectifs mentionnés du problème d'ordonnancement de tournée du personnel étudié. Les méthodes d'agrégation linéaire et de ε-contrainte sont appliquées pour résoudre ce modèle d'optimisation. En outre, cette thèse présente une nouvelle variante du problème d'affectation appelé problème d'affectation généralisée par séquence qui est défini pour la planification du personnel dans un système combiné constitué des postes de travail en série et en parallèle. Il est prouvé que ce problème d'optimisation combinatoire est NP-difficile et les méthodes exactes ne sont pas capables de résoudre les instances de grande taille. Ainsi, trois méthodes approchées composées de deux approches matheuristiques et une heuristique hybride sont développées pour résoudre ce problème. Les méthodes matheuristiques sont basées sur la décomposition de la formulation pour simplifier le modèle principal en deux ou plusieurs modèles plus petits. La troisième méthode est une heuristique gloutonne combinée à une recherche locale. En outre, dans la dernière étape de cette thèse, la planification des ressources humaines pour un système de soins à domicile est formulée mathématiquement. Selon la structure du système, une intégration des problèmes d'affectation et de tournées de véhicules est présentée. Enfin, une approche matheuristique en trois étapes est proposée pour résoudre ce problème d'optimisation combinatoire.

Les modèles graphiques probabilistes unifient la théorie des probabilités et les modèles graphiques via des variables aléatoires reliées entre elles par une distribution de loi jointe décomposable. L’objectif étudié ici est connu sous le nom de Maximum A Posteriori dans les champs aléatoires de Markov et de Most Probable Explanation dans les réseaux bayésiens, consiste à trouver une affectation globale de toutes les variables ayant une probabilité maximale ou de manière équivalente une énergie minimale. Les méthodes de résolution MAP/MPE sont qualifiées habituellement de complète ou incomplète, selon leur capacité à prouver l’optimalité ou non. Alors que la plupart des méthodes complètes reposent sur la recherche arborescente, les méthodes incomplètes reposent, quant à elles, sur la recherche locale. Dans cet article, nous proposons une approche itérative potentiellement complète au-dessus d’une recherche à voisinages variables qui utilise la recherche arborescente partielle dans son exploration locale des voisinages. La méthode hybride qui en résulte a été evaluée sur un large éventail de benchmarks issus de l’analyse d’images, la reconnaissance de formes, l’allocation de ressources, la bio-informatique, la bio-physique. . . Les résultats montrent que comparée aux méthodes de recherche arborescente existantes, notre méthode offre un meilleur compromis entre le comportement anytime et la preuve d’optimalité. Enfin, l’expérimentation de notre version parallèle sur des instances difficiles issues de la conception de protéines a mis en évidence l’efficacité de la version parallèle pour trouver des bonnes solutions. Le solveur est librement téléchargeable sur https:/ / github.com/ toulbar2/ toulbar2., Graphical models factorize a global probability distribution/energy function as the product/sum of local functions. A major inference task, known as MAP in Markov Random Fields and MPE in Bayesian Networks, is to find a global assignment of all the variables with maximum probability/minimum energy. A usual distinction on MAP/MPE solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighborhood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS which uses (partial) tree search inside its local neighborhood exploration. The resulting hybrid method offers a better compromise between completeness and anytime behavior than existing tree search methods while still being competitive for proving optimality. We further propose a parallel version of our method improving its anytime behavior on difficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. Solver is available at https:/ / github.com/ toulbar2/ toulbar2.

The analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimization. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of classical combinatorial optimization problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/epsilon²) gives a (1 + epsilon)-approximation with running time n^{O(1/epsilon²)}. However the question of whether the exponent of n could be decreased to o(1/epsilon²) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results, L'analyse des techniques d'approximation est centrale en géométrie algorithmique, pour des raisons pratiques comme théoriques. Dans cette thèse nous traitons de l'échantillonnage des structures géométriques et des algorithmes d'approximation géométriques en optimisation combinatoire. La première partie est consacrée à la combinatoire des hypergraphes. Nous débutons par les problèmes de packing, dont des extensions d'un lemme de Haussler, particulièrement le lemme dit de Shallow packing, pour lequel nous donnons aussi un minorant optimal, conjecturé mais pas établi dans les travaux antérieurs. Puis nous appliquons ledit lemme, avec la méthode de partition polynomiale récemment introduite, à l'étude d'un analogue combinatoire des régions de Macbeath de la géométrie convexe : les M-réseaux, pour lesquels nous unifions les résultats d'existence et majorations existants, et donnons aussi quelques minorants. Nous illustrons leur relation aux epsilon-réseaux, structures incontournables en géométrie combinatoire et algorithmique, notamment en observant que les majorants de Chan et al. (SODA 2012) ou Varadarajan (STOC 2010) pour les epsilon-réseaux (uniformes) découlent directement de nos résultats sur les M-réseaux. La deuxième partie traite des techniques de recherche locale appliquées aux restrictions géométriques de problèmes classiques d'optimisation combinatoire. En dix ans, ces techniques ont produit les premiers schémas d'approximation en temps polynomial pour divers problèmes tels que celui de calculer un plus petit ensemble intersectant pour un ensemble de disques donnés en entrée parmi un ensemble de points donnés en entrée. En fait, il a été montré que pour de nombreux tels problèmes, la recherche locale de rayon Θ (1/epsilon²) donne une (1 + epsilon)-approximation en temps n^{O(1/epsilon²)}. Savoir si l'exposant de n pouvait être ramené à o (1/epsilon²) demeurait une question ouverte. Nous répondons par la négative : la garantie d'approximation de la recherche locale n'est améliorable pour aucun desdits problèmes

Production is always in perpetual evolution. Indeed, company needs to adapt its performance to market fluctuations (random requests) and internal perturbations within its systems (breakdowns, absenteeism, etc.). To cope with these uncertainties, permanent production management benefiting from the power of computer technology is fundamental. The scheduling of production is one of optimization’s tools contributing to the improvement of productivity in front of hazards. In this context, the objective is to define scheduling policies, taking into account the unavailability of resources (management of maintenance, human resources, etc.). In this thesis, we are particularly interested in the study of the two-machine job shop scheduling problems with resources not always available. The aim of our work is to propose methods for exact and approximate resolution for this type of problem, exploiting as much as possible theoretical properties for the minimization of the total completion time (makespan) which is to maximize the productivity, Dans un contexte de production en perpétuelle évolution, l’entreprise est tenue à s’adapter en permanence aux fluctuations des marchés (demandes aléatoires) et aux perturbations internes de ses systèmes (pannes, absentéisme, ...). Face à ces incertitudes, la gestion de production permanente bénéficiant également de la puissance de la technologie informatique est indispensable. L’ordonnancement des ateliers de production est l’un des axes d’optimisation contribuant à l’amélioration de la productivité face aux aléas. Il s’agit dans ce contexte de définir les politiques d’ordonnancement avec la prise en compte de l’indisponibilité des ressources (gestion de la maintenance, de ressources humaines ...). Dans cette thèse, nous nous intéressons plus particulièrement aux problèmes d’ordonnancement d’atelier à chemins multiples (Job shop) à deux machines avec des ressources non disponibles en permanence. Le but de nos travaux est de proposer des méthodes de résolution exactes et approchées pour ce type de problèmes, exploitant autant que possible des propriétés théoriques pour la minimisation du makespan qui revient à maximiser la productivité

This thesis studies Stochastic Vehicle Routing Problems (SVRPs) in the context of maintenance tasks scheduling. Stochastic programming under an A Priori paradigm is used to incorporate the uncertainties. Two SVRPs are addressed, the first one deals with Stochastic Demands which is solved by a hybrid approach combining a memetic algorithm (MA) and a Greedy Randomized Adaptive Search Procedure (GRASP). The designed hybrid method is shown to be competitive compared to other published approaches. Second, the SVRP with stochastic travel and service times and hard time windows investigated. A parallel Memetic Algorithm is designed to solve efficiently this last problem. A third problem devoted to maintenance scheduling in wind farm context is also studied in this work. First the problem is formulated as a deterministic linear bicriteria mixed integer program, then an epsilon constraint is developed to solve it. An extension to a maintenance planning problem involving a long horizon is also addressed using a simulation approach. This last part also considers maintenance strategies selection. Both developed approaches show the existing conflicts between energy production maximization and maintenance costs minimization, Cette thèse est dédiée aux problèmes de tournées de véhicules stochastiques (SVRP) abordés dans un contexte de planification de tâches de maintenance. Le paradigme de solutions À Priori est choisi pour inclure les incertitudes au moment de la planification. Deux SVRP sont étudiés, d’abord le problème avec demandes stochastiques, qui est résolu par un algorithme mémétique (MA) hybridé avec une procédure de recherche adaptative randomisée. La méthode s’est montrée compétitive en comparaison à d’autres approches disponibles dans la littérature. Ensuite le SVRP avec fenêtre de temps sur le service, et temps de trajets et de services stochastiques est considéré. Un algorithme mémétique parallèle est conçu pour le résoudre efficacement. Un troisième problème traitant de l’ordonnancement de la maintenance pour un parc d’éoliennes est étudié dans cette thèse. D’abord une version déterministe et bi-objective est modélisée sous forme d’un programme linéaire à variables mixtes, puis résolue par une méthode de type epsilon contraintes. Une extension du problème sur un horizon de planification long et considérant les stratégies de maintenance est également proposée, et le problème est résolu par une méthode basée sur la simulation. Les méthodes développées mettent en évidence, pour les deux derniers problèmes, le conflit entre la minimisation des coûts de maintenance et la maximisation de la production énergétique

The increase of the traffic flow in urban areas has a strong impact on the infrastructures of transportation networks. The situation becomes more complex whenever disruptions occur on the road networks, which often reduce the traffic capacity. This thesis comprises two major goals. The first objective consists of an academic study on Road Network problems with Disruptions and connecting requirements (RND). The other one is dedicated to the software engineering of a decision-support system, named Optimal traffic Deviation System (ODS). Depending on the network structure, RND is specialized into two problems: Unidirectional RND and Multidirectional RND. Multi-flow mathematical models are proposed for both problems, i.e. URND and MRND. Moreover, a Biased Random Key Genetic Algorithm (BRKGA) and an Iterated Local Search (ILS) metaheuristics are developed for the mono-objective RND versions, and then adaptations of these methods are proposed for the URND and MRND bi-objectives. In addition, classical bi-objective methods such as Non-dominated Sorting Genetic Algorithm II and -constraint are also developed. Results indicate mono and bi-objective ILS overcome the other methods. The decision-making system ODS is connected to heterogeneous systems for collecting the geographical data and to get a set of disruptions from Troyes city. Moreover, several constraints and optimization criteria are taken into account in the dedicated algorithms in order to propose detouring solutions, L'augmentation du flux de trafic dans des zones urbaines a un fort impact sur les infrastructures de réseaux de transport. La situation devient encore plus compliquée lorsqu’il y a des interruptions qui perturbent la circulation. Dans cette thèse, deux objectifs majeurs sont ciblés : le premier consiste à l’étude du problème de conception de réseau routier avec des interruptions tout en assurant la forte connexité du réseau (RND) ; le second porte sur le développement du système d’aide à la décision : Optimal traffic Deviation System (ODS). En fonction de la nature du réseau, RND est spécialisé en Unidirectionnel RND et Multidirectionnel RND. Des modèles mathématiques multi-flot sont proposés pour ces problèmes. De plus, des méta-heuristiques du type Biased Random Key Genetic Algorithm (BRKGA) et Iterated Local Search (ILS) sont développées pour les problèmes en versions mono-objectif. Des adaptations pour ces méthodes sont ensuite proposées pour traiter les problèmes en version bi-objectif. En outre, des méthodes multi-objectif classiques sont également développées, telles que la méthode -constraint et Non-dominated Sorting Genetic Algorithm II. Les résultats numériques indiquent que l’ILS dans les versions mono et bi-objectif produit les meilleurs résultats que les autres méthodes. Enfin, le système ODS est connecté à des systèmes hétérogènes de données géographiques et à la base des arrêtés municipaux de la ville de Troyes, incluant plusieurs contraintes, critères d’optimisation et algorithmes dédiés permettant de proposer des déviations

Biomass can play a crucial role as one of the main sources of renewable energies. As logistics holds a significant share of biomass cost, efficient biomass supply chains must be designed to provide bio-refineries with adequate quantities of biomass at reasonable prices and appropriate times. This thesis focuses on modeling and optimization of multi-biomass supply chains for several bio-refineries. A data model is developed to list, analyze and structure the set of required data, in a logical way. The result is a set of tables that can be loaded into mathematical models for solving optimization problems. Then, a multi-period mixed integer linear programming model is proposed to optimize a multi-biomass supply chains for several bio-refineries, at the tactical and strategic level. Refineries can be already placed or located by the model. The aim is to minimize the total costs, including biomass production, storage, handling, refineries setup and transportation costs, while satisfying the demand of refineries in each period. Additionally, a multi-objective model is developed to optimize simultaneously the economic and environmental performance of biomass supply chains. The model is solved by using the ε-constraint method. Furthermore, large-scale tests on real data for two regions of France (Picardie & Champagne-Ardenne) are prepared to evaluate the proposed models. Finally, two-phase approaches are proposed to solve large-scale instances in reasonable running times, while evaluating the loss of optimality compared to the exact model, La biomasse peut jouer un rôle crucial comme source d'énergie renouvelable. La logistique représentant une part importante du coût, des chaînes d'approvisionnement efficaces doivent être conçues pour fournir aux bio-raffineries les quantités demandées, à des prix raisonnables et à des moments adéquats. Cette thèse porte sur la modélisation et l'optimisation de chaînes logistiques de biomasse pour plusieurs raffineries. Un modèle de données est élaboré pour structurer les informations nécessaires à une base de données alimentant les modèles mathématiques. Ensuite, un modèle linéaire multi-période à variables mixtes est proposé pour optimiser au niveau tactique et stratégique une chaîne logistique multi-biomasse. Les emplacements des raffineries peuvent être prédéfinis ou déterminés par le modèle. L'objectif est de minimiser un coût total incluant la production de biomasse, le stockage, la manutention, la création des raffineries et le transport, tout en satisfaisant les besoins des raffineries dans chaque période. Une version multi-objective est développée pour optimiser simultanément des critères économiques et environnementaux. Elle est résolue par une méthode de type ε-contrainte. Des grandes instances avec des données réelles pour deux régions de France (Picardie et Champagne Ardenne) sont préparées pour évaluer des modèles proposés. Enfin, des approches en deux phases sont appliquées pour résoudre les grands cas en un temps raisonnable, tout en évaluant l’écart à l’optimum fourni par la méthode exacte

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., 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.

Branch-and-Bound (B&B) is a frequently used tree-search exploratory method for the exact resolution of combinatorial optimization problems (COPs). However, in practice, only small problem instances can be solved on a sequential computer, as B&B generates often generates a huge amount of subproblems to be evaluated. In order to solve large COPs, we revisit the design and implementation of massively parallel B&B on top of large heterogeneous clusters, integrating multi-core CPUs, many-core processors and GPUs.For the efficient storage and management of subproblems an original data structure (IVM) dedicated to permutation problems is used. Because of the highly irregular and unpredictable shape of the B&B tree, dynamic load balancing between parallel exploration processes is one of the main issues addressed in this thesis. Based on a compact encoding of the search space in the form of intervals, work stealing strategies for multi-core and GPU are proposed, as well as hierarchical approaches for load balancing in distributed memory multi-CPU/multi-GPU systems. Three permutation problems, the Flowshop Scheduling Problem (FSP), the Quadratic Assignment Problem (QAP) and the n-Queens puzzle problem are used as test-cases.The resolution, in 9 hours, of a FSP instance with an estimated sequential execution time of 22 years demonstrates the scalability of the proposed algorithms on a cluster composed of 36 GPUs.; L'algorithme Branch-and-Bound (B&B) est une méthode de recherche arborescente fréquemment utilisé pour la résolution exacte de problèmes d'optimisation combinatoire (POC). Néanmoins, seules des petites instances peuvent être effectivement résolues sur une machine séquentielle, le nombre de sous-problèmes à évaluer étant souvent très grand. Visant la resolution de POC de grande taille, nous réexaminons la conception et l'implémentation d'algorithmes B&B massivement parallèles sur de larges plateformes hétérogènes de calcul, intégrant des processeurs multi-coeurs, many-cores et et processeurs graphiques (GPUs). Pour une représentation compacte en mémoire des sous-problèmes une structure de données originale (IVM), dédiée aux problèmes de permutation est utilisée. En raison de la forte irrégularité de l'arbre de recherche, l'équilibrage de charge dynamique entre processus d'exploration parallèles occupe une place centrale dans cette thèse. Basés sur un encodage compact de l'espace de recherche sous forme d'intervalles, des stratégies de vol de tâches sont proposées pour processeurs multi-core et GPU, ainsi une approche hiérarchique pour l'équilibrage de charge dans les systèmes multi-GPU et multi-CPU à mémoire distribuée. Trois problèmes d'optimisation définis sur l'ensemble des permutations, le problème d'ordonnancement Flow-Shop (FSP), d'affectation quadratique (QAP) et le problème des n-dames sont utilisés comme cas d'étude. La resolution en 9 heures d'une instance du FSP dont le temps de résolution séquentiel est estimé à 22 ans demontre la capacité de passage à l'échelle des algorithmes proposés sur une grappe de calcul composé de 36 GPUs.

Multiphysics simulation couple several computation phases. When they are run in parallel on memory-distributed architectures, minimizing the simulation time requires in most cases to balance the workload across computation units, for each computation phase. Moreover, the data distribution must minimize the induced communication.This problem can be modeled as a multi-criteria graph partitioning problem. We associate with each vertex of the graph a vector of weights, whose components, called “criteria”, model the workload of the vertex for each computation phase. The edges between vertices indicate data dependencies, and can be given a weight representing the communication volume transferred between the two vertices. The goal is to find a partition of the vertices that both balances the weights of each part for each criterion, and minimizes the “edgecut”, that is, the sum of the weights of the edges cut by the partition. The maximum allowed imbalance is provided by the user, and we search for a partition that minimizes the edgecut, among all the partitions whose imbalance for each criterion is smaller than this threshold.This problem being NP-Hard in the general case, this thesis aims at devising and implementing heuristics that allow us to compute efficiently such partitions. Indeed, existing tools often return partitions whose imbalance is higher than the prescribed tolerance.Our study of the solution space, that is, the set of all the partitions respecting the balance constraints, reveals that, in practice, this space is extremely large. Moreover, we prove in the mono-criterion case that a bound on the normalized vertex weights guarantees the existence of a solution, and the connectivity of the solution space. Based on these theoretical results, we propose improvements of the multilevel algorithm. Existing tools implement many variations of this algorithm. By studying their source code, we emphasize these variations and their consequences, in light of our analysis of the solution space.Furthermore, we define and implement two initial partitioning algorithms, focusing on returning a solution. From a potentially imbalanced partition, they successively move vertices from one part to another. The first algorithm performs any move that reduces the imbalance, while the second performs at each step the move reducing the most the imbalance. We present an original data structure that allows us to optimize the choice of the vertex to move, and leads to partitions of imbalance smaller on average than existing methods.We describe the experimentation framework, named Crack, that we implemented in order to compare the various algorithms at stake. This comparison is performed by partitioning a set of instances including an industrial test case, and several fictitious cases. We define a method for generating realistic weight distributions corresponding to “Particles-in-Cells”-like simulations. Our results demonstrate the necessity to coerce the vertex weights during the coarsening phase of the multilevel algorithm. Moreover, we evidence the impact of the vertex ordering, which should depend on the graph topology, on the efficiency of the “Heavy-Edge” matching scheme.The various algorithms that we consider are implemented in an open-source graph partitioning software called Scotch. In our experiments, Scotch and Crack returned a balanced partition for each execution, whereas MeTiS, the current most used partitioning tool, fails regularly. Additionally, the edgecut of the solutions returned by Scotch and Crack is equivalent or better than the edgecut of the solutions returned by MeTiS., Les simulations dites multi-physiques couplent plusieurs phases de calcul. Lorsqu'elles sont exécutées en parallèle sur des architectures à mémoire distribuée, la minimisation du temps de restitution nécessite dans la plupart des cas d'équilibrer la charge entre les unités de traitement, pour chaque phase de calcul. En outre, la distribution des données doit minimiser les communications qu'elle induit.Ce problème peut être modélisé comme un problème de partitionnement de graphe multi-critères. On associe à chaque sommet du graphe un vecteur de poids, dont les composantes, appelées « critères », modélisent la charge de calcul porté par le sommet pour chaque phase de calcul. Les arêtes entre les sommets, indiquent des dépendances de données, et peuvent être munies d'un poids reflétant le volume de communication transitant entre les deux sommets. L'objectif est de trouver une partition des sommets équilibrant le poids de chaque partie pour chaque critère, tout en minimisant la somme des poids des arêtes coupées, appelée « coupe ». Le déséquilibre maximum toléré entre les parties est prescrit par l'utilisateur. On cherche alors une partition minimisant la coupe, parmi toutes celles dont le déséquilibre pour chaque critère est inférieur à cette tolérance.Ce problème étant NP-Dur dans le cas général, l'objet de cette thèse est de concevoir et d'implanter des heuristiques permettant de calculer efficacement de tels partitionnements. En effet, les outils actuels renvoient souvent des partitions dont le déséquilibre dépasse la tolérance prescrite.Notre étude de l'espace des solutions, c'est-à-dire l'ensemble des partitions respectant les contraintes d'équilibre, révèle qu'en pratique, cet espace est immense. En outre, nous prouvons dans le cas mono-critère qu'une borne sur les poids normalisés des sommets garantit que l'espace des solutions est non-vide et connexe. Nous fondant sur ces résultats théoriques, nous proposons des améliorations de la méthode multi-niveaux. Les outils existants mettent en œuvre de nombreuses variations de cette méthode. Par l'étude de leurs codes sources, nous mettons en évidence ces variations et leurs conséquences à la lumière de notre analyse sur l'espace des solutions.Par ailleurs, nous définissons et implantons deux algorithmes de partitionnement initial, se focalisant sur l'obtention d'une solution à partir d'une partition potentiellement déséquilibrée, au moyen de déplacements successifs de sommets. Le premier algorithme effectue un mouvement dès que celui-ci améliore l'équilibre, alors que le second effectue le mouvement réduisant le plus le déséquilibre. Nous présentons une structure de données originale, permettant d'optimiser le choix des sommets à déplacer, et conduisant à des partitions de déséquilibre inférieur en moyenne aux méthodes existantes.Nous décrivons la plate-forme d'expérimentation, appelée Crack, que nous avons conçue afin de comparer les différents algorithmes étudiés. Ces comparaisons sont effectuées en partitionnant un ensembles d'instances comprenant un cas industriel et plusieurs cas fictifs. Nous proposons une méthode de génération de cas réalistes de simulations de type « transport de particules ».Nos résultats démontrent la nécessité de restreindre les poids des sommets lors de la phase de contraction de la méthode multi-niveaux. En outre, nous mettons en évidence l'influence de la stratégie d'ordonnancement des sommets, dépendante de la topologie du graphe, sur l'efficacité de l'algorithme d'appariement « Heavy-Edge Matching » dans cette même phase. Les différents algorithmes que nous étudions sont implantés dans un outil de partitionnement libre appelé Scotch. Au cours de nos expériences, Scotch et Crack renvoient une partition équilibrée à chaque exécution, là où MeTiS, l'outil le plus utilisé actuellement, échoue une grande partie du temps. Qui plus est, la coupe des solutions renvoyées par Scotch et Crack est équivalente ou meilleure que celle renvoyée par MeTiS.