La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques. / Integer linear programming is a robust and efficient approach to solve large-scale instances of combinatorial problems. However, problems constantly gain in complexity and sometimes impose strong constraints on computation times. We must then develop specialised methods to compute heuristic primal solutions to the problem and derive lower bounds on the optimal value, and thus prove the quality of our primal solutions. We propose to guide a reformulation approach for mixed integer programs with Lagrangian relaxations. After the identification of a strong relaxation, a mechanical process leads to a second integer formulation. This reformulation is equivalent to the initial one, but its linear relaxation is equivalent to the strong Lagrangian dual. We will show that the reformulation approach unifies and generalises prior formulations and lower bounding approaches, and that it exposes a simple mechanism to reduce the size of reformulations in return for weaker bounds. Nevertheless, our reformulations are large. We address this issue by solving their linear relaxations with specialised methods. Finally, we apply the reformulation approach to two location problems. This yields novel formulations for both problems; some are very large but, thanks to the aforementioned specialised methods, still practical.

In this thesis, we introduce the Partitioning-Hub Location-Routing problem (PHLRP), which can be classified as a variant of the hub location problem.<p>PHLRP consists of partitioning a network into sub-networks, locating at least one hub in each subnetwork and routing the traffic within the network such that all inter-subnetwork traffic is routed through the hubs and all intra-subnetwork traffic stays within the sub-networks all the way from the source to the destination. Obviously, besides the hub location component, PHLRP also involves a graph partitioning component and a routing component. PHLRP finds applications in the strategic planning or deployment of the Intermediate System-Intermediate System (ISIS) Internet Protocol networks and the Less-than-truck load freight distribution systems.<p><p>First, we introduce three IP formulations for solving PHLRP. The hub location component and the graph partitioning components of PHLRP are<p>modeled in the same way in all three formulations. More precisely, the hub location component is represented by the p-median variables and constraints; and the graph partitioning component is represented by the size-constrained graph partitioning variables and constraints. The formulations differ from each other in the way the peculiar routing requirements of PHLRP are modeled.<p><p>We then carry out analytical and empirical comparisons of the three IP<p>formulations. Our thorough analysis reveals that one of the formulations is<p>provably the tightest of the three formulations. We also show analytically that the LP relaxations of the other two formulations do not dominate each other. On the other hand, our empirical comparison in a standard branch-and-cut framework that is provided by CPLEX shows that not the tightest but the most compact of the three formulations yield the best performance in terms of solution time. <p><p>From this point on, based on the insight gained from detailed analysis of the formulations, we focus our attention on a common sub-problem of the three formulations: the so-called size-constrained graph partitioning problem. We carry out a detailed polyhedral analysis of this problem. The main benefit from this polyhedral analysis is that the facets we identify for the size-constrained graph partitioning problem constitute strong valid inequalities for PHLRP.<p><p>And finally, we wrap up our efforts for solving PHLRP. Namely, we present<p>the results of our computational experiments, in which we employ some facets<p>of the size-constrained graph partitioning polytope in a branch-and-cut algorithm for solving PHLRP. Our experiments show that our approach brings<p>significant improvements to the solution time of PHLRP when compared with<p>the default branch-and-cut solver of XPress. <p><p>/<p><p>Dans cette thèse, nous introduisons le problème Partitionnement-Location des Hubs et Acheminement (PLHA), une variante du problème de location de hubs. Le problème PLHA partitionne un réseau afin d'obtenir des sous-réseaux, localise au moins un hub dans chaque sous-réseau et achemine le traffic dans le réseau de la maniére suivante :le traffic entre deux<p>sous-réseaux distincts doit être éxpedié au travers des hubs tandis que le traffic entre deux noeuds d'un même sous-réseau ne doit pas sortir de celui-ci. PLHA possède des applications dans le planning stratégique, ou déploiement, d'un certain protocole de communication utilisé<p>dans l'Internet, Intermediate System - Intermediate System, ainsi que dans la distribution des frets.<p><p>Premièrement, nous préesentons trois formulations linéaires en variables entières pour résoudre PLHA. Le partitionnement du graphe et la localisation des hubs sont modélisées de la même maniére dans les trois formulations. Ces formulations diffèrent les unes des autres dans la maniére dont l'acheminement du traffic est traité.<p><p>Deuxièmement, nous présentons des comparaisons analytiques et empiriques des trois formulations. Notre comparaison analytique démontre que l'une des formulations est plus forte que les autres. Néanmoins, la comparaison empirique des formulations, via le solveur CPLEX, montre que la formulation la plus compacte (mais pas la plus forte) obtient les meilleures performances en termes de temps de résolution du problème.<p><p>Ensuite, nous nous concentrons sur un sous-problème, à savoir, le partitionnement des graphes sous contrainte de taille. Nous étudions le polytope des solutions réalisables de ce sous-problème. Les facettes de ce polytope constituent des inégalités valides fortes pour<p>PLHA et peuvent être utilisées dans un algorithme de branch-and-cut pour résoudre PLHA.<p><p>Finalement, nous présentons les résultats d'un algorithme de branch-and-cut que nous avons développé pour résoudre PLHA. Les résultats démontrent que la performance de notre méthode est meilleure que celle de l'algorithme branch-and-cut d'Xpress.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

La gestion de l’énergie est une préoccupation majeure dans les réseaux de capteurs sans fil. Ces capteurs sont généralement alimentés par une batterie embarquant une quantité d’énergie finie. Par conséquent, le temps pendant lequel les capteurs peuvent surveiller une zone et communiquer par signaux radio peut être limitée lorsqu’il n’est pas possible de remplacer leur batterie. En outre, les réseaux de capteurs sont parfois déployés dans les zones difficiles d’accès ou dans des environnements hostiles dans lesquels le placement des capteurs peut être considéré comme aléatoire (c’est le cas par exemple lorsque les capteurs sont largués d’un avion ou d’un hélicoptère). Ainsi, l’emplacement des capteurs n’est pas connu a priori et les approches pour utiliser efficacement l’énergie sont nécessaires. Cette thèse explore l’utilisation de la génération colonnes pour optimiser l’utilisation de l’énergie dans les réseaux de capteurs sans fil. La génération de colonnes peut être vue comme un cadre général pour résoudre différents problèmes dans la conception et l’exploitation de ces réseaux. Plusieurs versions du problème et divers modèles sont proposés pour représenter leur fonctionnement,en utilisant notamment la génération de colonnes. Ces approches exploitent le caractère naturel de la génération de colonnes pour modéliser les différents aspects des réseaux de capteurs sans fil.Dans cette thèse, des contributions algorithmiques sont apportées afin de tirer le meilleur parti de la génération de colonnes au plan de l’efficacité computationnelle. Des stratégies hybrides combinant génération de colonnes et (méta)-heuristiques et donnant lieu à des méthodes exactes et approchées sont proposées et évaluées. Des tests numériques montrent l’efficacité des approches proposées et des bornes supérieures qui peuvent être employées pour évaluer l’efficacité des méthodes centralisées et distribuées. Enfin, des perspectives sont dégagées concernant les performances et la portabilité de la génération de colonnes pour aborder des problèmes plus réalistes et tenir compte des caractéristiques des réseaux de capteurs sans fil du futur. / Energy is a major concern in wireless sensor networks (WSN). These devices are typically battery operated and provided with a limited amount of energy. As a consequence, the time during which sensors can monitor the interesting phenomena and communicate through wireless signals might be limited because of (sometimes) irreplaceable batteries. Additionally, it is very common for WSN to be usedin remote or hostile environments which possibly makes necessary a random placement strategy (by using an airplane, a drone or a helicopter). Hence, the sensors location is not known a priori and approaches to efficiently use the energy are needed to answer to network topologies only known after sensors deployment. This thesis explores the use of column generation to efficiently use the energy in WSN. It is shown that column generation can be used as a general framework to tackle different problems in WSN design. Several versions of the problem and models for the operation of the WNS are adapted to be solved through column generation. These approaches take advantage of the natural way that column generation offers to consider different features of the WSN operation. Additionally, some computational improvements are proposed to keep the column generation method operating as an efficient exact approach. Hybrid strategies combining column generation with (meta)heuristic and exact approaches are considered and evaluated. The computational experiments demonstrate the efficiency of the proposed approaches and provide practitioners on WSN research with strategies to compute upper bounds to evaluate heuristic centralized and decentralized approaches. Finally, some future directions of research are provided based on the performance and adaptability of column generation to consider more sophisticated models and characteristics newly introduced in sensor devices.

Le traitement médical de choix pour la maladie rénale chronique est la transplantation d'organe. Cependant, plusieurs patients ne sont en mesure que de trouver un donneur direct avec lequel ils ne sont pas compatibles. Les Programmes de Don Croisé de Reins peuvent aider plusieurs paires donneur-patient incompatibles à échanger leur donneur entre elles. Typiquement, l'objectif principal d'un tel programme est de maximiser le nombre total de transplantations qui seront effectuées grâce à un plan d'échange. Plusieurs solutions optimales peuvent co-exister et comme la plupart correspondent à différents ensembles de patients obtenant un donneur compatible, il devient important de considérer quels individus seront sélectionnés. Fréquemment, ce problème n'est pas abordé et la première solution fournie par un solveur est choisie comme plan d'échange. Ceci peut mener à des parti-pris en faveur ou défaveur de certains patients, ce qui n'est pas considéré une approche juste. De plus, il est de la responsabilité des informaticiens de s'assurer du contrôle des résultats fournis par leurs algorithmes. Pour répondre à ce besoin, nous explorons l'emploi de multiples solutions optimales ainsi que la manière dont il est possible de sélectionner un plan d'échange parmi celles-ci. Nous proposons l'emploi de politiques aléatoires pour la sélection de solutions optimales suite à leur enumération. Cette tâche est accomplie grâce à la programmation en nombres entiers et à la programmation par contraintes. Nous introduisons aussi un nouveau concept intitulé équité individuelle. Ceci a pour but de trouver une politique juste pouvant être utilisée en collaboration avec les solutions énumerées. La mise à disposition de plusieurs métriques fait partie intégrante de la méthode. En faisant usage de la génération de colonnes en combinaison au métrique $L_1$, nous parvenons à applique la méthode à de plus larges graphes. Lors de l'évaluation de l'équité individuelle, nous analysons de façon systématique d'autres schémas d'équité tels que le principle d'Aristote, la justice Rawlsienne, le principe d'équité de Nash et les valeurs de Shapley. Nous étudions leur description mathématiques ainsi que leurs avantages et désavantages. Finalement, nous soulignons le besoin de considérer de multiples solutions, incluant des solutions non optimales en ce qui concerne le nombre de transplantations d'un plan d'échange. Pour la sélection d'une politique équitable ayant comme domaine un tel ensemble de solutions, nous notons l'importance de trouver un équilibre entre les mesures d'utilité et d'équité d'une solution. Nous utilisons le Programme de Bien-être Social de Nash afin de satisfaire à un tel objectif. Nous proposons aussi une méthodologie de décomposition qui permet d'étendre le système sous-jacent et de faciliter l'énumeration de solutions. / The preferred treatment for chronic kidney disease is transplantation. However, many patients can only find direct donors that are not fully compatible with them. Kidney Exchange Programs (KEPs) can help these patients by swapping the donors of multiple patient-donor pairs in order to accommodate them. Usually, the objective is to maximize the total number of transplants that can be realized as part of an exchange plan. Many optimal solutions can co-exist and since a large part of them features different subsets of patients that obtain a compatible donor, the question of who is selected becomes relevant. Often, this problem is not even addressed and the first solution returned by a solver is chosen as the exchange plan to be performed. This can lead to bias against some patients and thus is not considered a fair approach. Moreover, it is of the responsibility of computer scientists to have control of the output of the algorithms they design. To resolve this issue, we explore the use of multiple optimal solutions and how to pick an exchange plan among them. We propose the use of randomized policies for selecting an optimal solution, first by enumerating them. This task is achieved through both integer programming and constraint programming methods. We also introduce a new concept called individual fairness in a bid to find a fair policy over the enumerated solutions by making use of multiple metrics. We scale the method to larger instances by adding column generation as part of the enumeration with the $L_1$ metric. When evaluating individual fairness, we systematically review other fairness schemes such as Aristotle's principle, Rawlsian justice, Nash's principle of fairness, and Shapley values. We analyze their mathematical descriptions and their pros and cons. Finally, we motivate the need to consider solutions that are not optimal in the number of transplants. For the selection of a good policy over this larger set of solutions, we motivate the need to balance utility and our individual fairness measure. We use the Nash Social Welfare Program in order to achieve this, and we also propose a decomposition methodology to extend the machinery for an efficient enumeration of solutions.

Les rapports d’activité de l’Établissement Français du Sang (EFS) font état d’une demande croissante de produits sanguins labiles (PSL) tels les concentrés globules rouges (CGR), les plaquettes, et le plasma. Afin d’assurer la demande vitale en PSL, il est primordial d’optimiser la logistique liée aux activités de collecte du sang et de ses composants. Pour faire face à cette situation, l’EFS Auvergne-Loire mène une réflexion dans le but d’utiliser de manière plus efficiente les dispositifs de collecte en sites fixes et mobiles pour améliorer (i) la qualité de service rendue au donneur, et (ii) l’efficience de l’utilisation des ressources humaines. Dans ce contexte nous avons développé dans cette thèse des outils opérationnels pour (i) la modélisation des dispositifs de collecte, (ii) la régulation des flux de donneurs, et (iii) la planification de collectes mobiles.La méthode d'analyse des dispositifs de collecte est basée sur des techniques de simulation à événements discrets. Une modélisation préalable des flux de donneurs dans les systèmes de collecte en sites fixes et mobiles à l’aide de réseaux de Petri a été proposée. Pour la régulation de flux de donneurs, notamment pour la planification optimale des rendez-vous des donneurs et la planification de la capacité dans les systèmes de collecte au site fixe, deux approches ont été abordées: (a) Construction d'un algorithme basée sur techniques d'optimisation stochastique via simulation ; (b) Programmation mathématique: Modèle de programmation en nombres entiers non-linéaire (MINLP) basée sur réseaux de files d'attente et représentation et évaluation des systèmes à événements discrets à travers de programmation mathématique. Pour la planification de collectes mobiles. Deux types de modèles ont été développés : (a) Au niveau tactique : Modèles de programmation en nombres entiers linéaire (MIP) pour planifier les semaines de collectes pour chaque ensemble disponible sur un horizon de temps pour garantir l'autosuffisance à niveau régional des CGR. (b) Au niveau opérationnel : Modèle de programmation en nombres entiers linéaire (MIP) pour l’organisation du travail des équipes en charge de la collecte. / Activity reports of the French Blood Establishment (EFS) indicate a growing demand for Labile Blood Products (LBP) as red blood cells (RBC), platelets and plasma. To ensure the vital demand of labile blood products (LBP), it’s essential to optimize the logistics related with the collection of blood components. To deal with this situation, the EFS Auvergne-Loire carry out a reflection in order to use more efficiently the collection devices in fixed and mobile sites, to improve the quality of service offered to the donor and the efficiency of human resources. In this context we have developed in this thesis operational tools for (i) modeling of blood collection devices (ii) The regulation of flows donors (iii) Planning of bloodmobile collections.The method analysis of collection devices is based on techniques of discrete event simulation. A preliminary modeling of donors’ flow in fixed and mobile collection systems using Petri nets was conducted. For the regulation of flow of donors, i.e. the optimal capacity planning and appointment scheduling of blood collections, two approaches were considered: (a) Simulation based-optimization.(b) Mathematical Programming: Mixed integer nonlinear programming (MINLP) based on queuing networks and mathematical programming representation of discrete event systems. For planning of bloodmobile collections. Two models have been developed: (a) At the tactical level: Mixed integer linear programming (MIP) to determine the weeks in which the mobile collection must be organized in order to ensure the regional self-sufficiency of RBC. (b) At the operational level: Mixed integer linear programming (MIP) for the planning of human resources in charge of blood collections.

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes. / The berth allocation problem (BAP) is one of the key decision problems at port terminals and it has been widely studied. In previous research, the BAP has been formulated as a generalized set partitioning problem (GSPP) and solved using standard solver. The assignments (columns) were generated a priori in a static manner and provided as an input to the optimization model. The GSPP approach is able to solve to optimality relatively large size problems. However, a main drawback of this approach is the explosion in the number of feasible assignments of vessels with increase in problem size which leads in turn to the optimization solver to run out of memory. In this research, we address the limitation of the GSPP approach and present a column generation framework where assignments are generated dynamically to solve large problem instances of the berth allocation problem at port terminals. We propose a column generation based algorithm to address the problem that can be easily adapted to solve any variant of the BAP based on different spatial and temporal attributes. We test and validate the proposed approach on a discrete berth allocation model with dynamic vessel arrivals and berth dependent handling times. Computational experiments on a set of artificial instances indicate that the proposed methodology can solve even very large problem sizes to optimality or near optimality in computational time of only a few minutes.

No description available.

No description available.

L'augmentation de la concurrence économique internationale et les attentes accrues des clients ont imposé aux entreprises de prendre en compte non seulement le prix ou la qualité du produit, mais également la fiabilité et la rapidité des livraisons. Dans les industries ayant une composante manufacturière dominante telles que l'automobile et l'électronique, la distribution et les coûts de stockage constituent les deuxième et troisième catégories de coûts les plus importantes après les coûts de production. Par conséquent, les entreprises industrielles et de logistique recherchent continuellement des méthodes pour réduire le niveau des stocks et les coûts de distribution. Cette tendance a créé une interaction plus forte entre les différentes étapes de la chaîne logistique, et augmente de ce fait l'utilité pratique des modèles intégrés.Cette thèse considère deux catégories de problèmes d'ordonnancement intégré. La première catégorie est l'ordonnancement intégré de la production, distribution et stockage (Integrated Scheduling of Production-Distribution-Inventory, ISPDI) et la deuxième est l'ordonnancement intégré de la production, stockage, distribution et stockage (Integrated Scheduling of Production-Inventory-Distribution-Inventory, ISPIDI). Au niveau de la production, les tâches à réaliser sont traitées sur une seule machine et regroupées par lot de production, ce qui nécessite un coût et un temps de réglage. Elles doivent ensuite être livrées à un client prédéfini par un transporteur à capacité limitée, avant des dates dues données. Chaque aller-retour du transporteur entre l'usine et le client implique un coût de livraison et des délais de livraison. De plus, on suppose que les tâches qui sont terminées avant leur date de départ ou qui sont livrées au client avant leur date due entraînent un coût de stockage supplémentaire. Notre objectif est de minimiser le coût total comprenant les coûts de reglage, de stockage et de transport, tout en garantissant un niveau de service donné pour le client.Pour les problèmes ISPDI, nous avons d'abord fourni un modèle de programmation mixte entière pour le problème multi-produits, à un seul niveau, et avons développé un algorithme génétique amélioré pour le résoudre. Puis, nous avons modifié ce modèle pour prendre en compte le cas mono-produit, multi-niveau, et avons proposé deux méthodes, un algorithme hybride et un algorithme génétique, pour le résoudre. Pour les problèmes ISPIDI, nous avons établi un modèle général non-linéaire dans le cas mono-produit, et avons traité un cas spécifique du cas général. Puis nous avons démontré une propriété d'optimalité qui lie les ordonnancements de production et de livraison dans le cas particulier, pour finalement proposer une approche heuristique pour le résoudre. Pour chaque problème étudié et afin d'évaluer la performance des algorithmes proposés, des limites inférieures intéressantes sur les fonctions objectifs correspondantes ont été établies selon des méthodes différentes telles que la méthode de relaxation lagrangienne ou des méthodes basées sur les bornes inférieures du problème de bin packing. Les résultats des expérimentations montrent l'efficacité des modèles et algorithmes proposés en termes de qualité de la solution et de temps d'exécution. / Increasing global competition in the business world and heightened expectations of customers have forced companies to consider not only the pricing or product quality, but reliability and timeliness of the deliveries as well. In manufacturing-centric industries such as automotive and electronics, distribution and inventory costs constitute the second and third largest cost components following the production costs. Therefore, industrial and logistics companies need to continuously search for ways to lower the inventory level and distribution cost. This trend has created a closer interaction between the different stages of a supply chain, and increased the practical usefulness of the integrated models.This thesis considers two categories of integrated scheduling problems. One is Integrated Scheduling of Production-Distribution-Inventory problems (ISPDI problems) and the other is Integrated Scheduling of Production-Inventory-Distribution-Inventory problems (ISPIDI problems). Jobs are first processed on a single machine in the production stage, and then delivered to a pre-specified customer by a capacitated transporter. Each job has a distinct due date, and must be delivered to customer before this due date. Each production batch requires a setup cost and a setup time before the first job of this batch is processed. Each round trip between the factory and customer requires a delivery cost as well as a delivery time. Moreover, it is assumed that a job which is completed before its departure date or delivered to the customer before its due date will incur a corresponding inventory cost. Our objective is to minimize the total cost involving setup, inventory and delivery costs while guaranteeing a certain customer service level.For ISPDI problems, we firstly provide a mixed integer programming model for the case of multi-product, single-stage situation, and develop an improved Genetic algorithm (GA) for solving it. Then, we extend this model to a single-product, multi-stage model, and provide two methods, dominance-related greedy algorithm and GA, for solving it. For ISPIDI problems, we establish a general non-linear model for the case of single-product situation and devise a special case from the general model. Then we provide an optimality property between the production and delivery schedules for the special case. Finally, a heuristic approach is developed for solving it. For each problem under study, in order to evaluate the performance of the proposed algorithms, some interesting lower bounds on the corresponding objective functions are established according to different methods such as Lagrangian relaxation method, classical bin-packing based method. Computational results show the efficiency of the proposed models and algorithms in terms of solution quality and running time.

No description available.