Ce travail de thèse de doctorat est dédié à l'étude d'un problème de placement de tâches dans le domaine de la compilation d'applications pour des architectures massivement parallèles. Ce problème vient en réponse à certains besoins industriels tels que l'économie d'énergie, la demande de performances pour les applications de type flots de données synchrones. Ce problème de placement doit être résolu dans le respect de trois critères: les algorithmes doivent être capable de traiter des applications de tailles variables, ils doivent répondre aux contraintes de capacités des processeurs et prendre en compte la topologie des architectures cibles. Dans cette thèse, les tâches sont organisées en réseaux de communication, modélisés sous forme de graphes. Pour évaluer la qualité des solutions produites par les algorithmes, les placements obtenus sont comparés avec un placement aléatoire. Cette comparaison sert de métrique d'évaluation des placements des différentes méthodes proposées. Afin de résoudre à ce problème, deux algorithmes de placement de réseaux de tâches de grande taille sur des architectures clusterisées de processeurs de type many-coeurs ont été développés. Ils s'appliquent dans des cas où les poids des tâches et des arêtes sont unitaires. Le premier algorithme, nommé Task-wise Placement, place les tâches une par une en se servant d'une notion d'affinité entre les tâches. Le second, intitulé Subgraph-wise Placement, rassemble les tâches en groupes puis place les groupes de tâches sur les processeurs en se servant d'une relation d'affinité entre les groupes et les tâches déjà affectées. Ces algorithmes ont été testés sur des graphes, représentants des applications, possédant des topologies de types grilles ou de réseaux de portes logiques. Les résultats des placements sont comparés avec un algorithme de placement, présent dans la littérature qui place des graphes de tailles modérée et ce à l'aide de la métrique définie précédemment. Les cas d'application des algorithmes de placement sont ensuite orientés vers des graphes dans lesquels les poids des tâches et des arêtes sont variables similairement aux valeurs qu'on peut retrouver dans des cas industriels. Une heuristique de construction progressive basée sur la théorie des jeux a été développée. Cet algorithme, nommé Regret Based Approach, place les tâches une par une. Le coût de placement de chaque tâche en fonction des autres tâches déjà placées est calculée. La phase de sélection de la tâche se base sur une notion de regret présente dans la théorie des jeux. La tâche qu'on regrettera le plus de ne pas avoir placée est déterminée et placée en priorité. Afin de vérifier la robustesse de l'algorithme, différents types de graphes de tâches (grilles, logic gate networks, series-parallèles, aléatoires, matrices creuses) de tailles variables ont été générés. Les poids des tâches et des arêtes ont été générés aléatoirement en utilisant une loi bimodale paramétrée de manière à obtenir des valeurs similaires à celles des applications industrielles. Les résultats de l'algorithme ont également été comparés avec l'algorithme Task-Wise Placement, qui a été spécialement adapté pour les valeurs non unitaires. Les résultats sont également évalués en utilisant la métrique de placement aléatoire. / This Ph.D thesis is devoted to the study of the mapping problem related to massively parallel embedded architectures. This problem arises from industrial needs like energy savings, performance demands for synchronous dataflow applications. This problem has to be solved considering three criteria: heuristics should be able to deal with applications with various sizes, they must meet the constraints of capacities of processors and they have to take into account the target architecture topologies. In this thesis, tasks are organized in communication networks, modeled as graphs. In order to determine a way of evaluating the efficiency of the developed heuristics, mappings, obtained by the heuristics, are compared to a random mapping. This comparison is used as an evaluation metric throughout this thesis. The existence of this metric is motivated by the fact that no comparative heuristics can be found in the literature at the time of writing of this thesis. In order to address this problem, two heuristics are proposed. They are able to solve a dataflow process network mapping problem, where a network of communicating tasks is placed into a set of processors with limited resource capacities, while minimizing the overall communication bandwidth between processors. They are applied on task graphs where weights of tasks and edges are unitary set. The first heuristic, denoted as Task-wise Placement, places tasks one after another using a notion of task affinities. The second algorithm, named Subgraph-wise Placement, gathers tasks in small groups then place the different groups on processors using a notion of affinities between groups and processors. These algorithms are tested on tasks graphs with grid or logic gates network topologies. Obtained results are then compared to an algorithm present in the literature. This algorithm maps task graphs with moderated size on massively parallel architectures. In addition, the random based mapping metric is used in order to evaluate results of both heuristics. Then, in a will to address problems that can be found in industrial cases, application cases are widen to tasks graphs with tasks and edges weights values similar to those that can be found in the industry. A progressive construction heuristic named Regret Based Approach, based on game theory, is proposed. This heuristic maps tasks one after another. The costs of mapping tasks according to already mapped tasks are computed. The process of task selection is based on a notion of regret, present in game theory. The task with the highest value of regret for not placing it, is pointed out and is placed in priority. In order to check the strength of the algorithm, many types of task graphs (grids, logic gates networks, series-parallel, random, sparse matrices) with various size are generated. Tasks and edges weights are randomly chosen using a bimodal law parameterized in order to have similar values than industrial applications. Obtained results are compared to the Task Wise placement, especially adapted for non-unitary values. Moreover, results are evaluated using the metric defined above.

Depuis une vingtaine d'années, la résolution de problèmes d'optimisation globale non convexes avec contraintes a connu un formidable essor. Les algorithmes de branch and bound basée sur l'analyse d'intervalles ont su trouver leur place, car ils ont l'avantage de prouver l'optimalité de la solution de façon déterministe, avec un niveau de certitude pouvant aller jusqu'à la précision machine. Cependant, la complexité exponentielle en temps et en mémoire de ces algorithmes induit une limite intrinsèque, c'est pourquoi il est toujours nécessaire d'améliorer les techniques actuelles. - Dans cette thèse, nous avons développé de nouvelles arithmétiques basées sur l'arithmétique d'intervalles et l'arithmétique affine, afin de calculer des minorants et des majorants de meilleure qualité de fonctions explicites sur un intervalle. - Nous avons ensuite développé une nouvelle méthode automatique de construction de relaxations linéaires. Cette construction est basée sur l'arithmétique affine et procède par surcharge des opérateurs. Les programmes linéaires ainsi générés ont exactement le même nombre de variables et de contraintes d'inégalité que les problèmes originaux, les contraintes d'égalité étant remplacées par deux inégalités. Cette nouvelle procédure permet de calculer des minorants fiables et des certificats d'infaisabilité pour chaque sous-domaine à chaque itération de notre algorithme de branch and bound par intervalles. De nombreux tests numériques issus du site COCONUT viennent confirmer l'efficacité de cette approche. - Un autre aspect de cette thèse a été l'étude d'une extension de ce type d'algorithmes en introduisant une limite sur mémoire disponible. L'idée principale de cette approche est de proposer un processus inverse de l'optimisation par le biais d'un principe métaheuristique: plutôt que d'améliorer des solutions locales à l'aide de métaheuristiques telles que les algorithmes Taboo ou VNS, nous partons d'une méthode exacte et nous la modifions en une heuristique. De cette façon, la qualité de la solution trouvée peut être évaluée. Une étude de la complexité de ce principe métaheuristique a également été effectuée. - Enfin, pour finir l'étude, nous avons appliqué notre algorithme à la résolution de problème en géométrie plane, ainsi qu'à la résolution d'un problème de dimensionnement de moteur électrique. Les résultats obtenus ont permis de confirmer l'intérêt de ce type d'algorithme, en résolvant des problèmes ouverts sur les polygones convexes et proposant des structures innovantes en génie électrique.

L'étude du domaine récent que constituent les problèmes d'optimisation combinatoires probabilistes (POCPs) forme le sujet de cette thèse. Les POCPs sont des généralisations des problèmes d'optimisation combinatoires classiques dont les formulations contiennent explicitement des éléments probabilistes. Plusieurs motivations ont provoqué cette étude. Deux d'entre elles sont particulièrement importantes. La première correspond au désir de formuler et d'analyser des modèles qui sont plus appropriés pour des problèmes pratiques pour lesquels l'aléatoire est une source constante de préoccupations, les modèles de nature probabiliste sont plus particulièrement attractifs comme abstraction mathématique des systèmes réels. La seconde motivation est d'analyser la stabilité des solutions optimales des problèmes déterministes lorsque les exemplaires sont perturbés : les perturbations sont simulées par la présence ou l'absence de sous-ensembles des données. Notre étude s'appuie sur certains de ces problèmes et en particulier : problème du voyageur de commerce; problème d'ordonnancement des travaux probabiliste et le problème du bin-packing probabiliste. Les questions soulevées et les résultats obtenus sont dans les domaines suivants : complexités des problèmes et analyse d'heuristiques pour les POCPs ; analyse du comportement asymptotique des problèmes lorsque les exemplaires correspondent à des problèmes de grandes tailles ; dégager une méthodologie générale d'étude de la stabilité des solutions des problèmes d'optimisation combinatoires classiques.

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48]. / The capacitated location-routing problem (CLRP) arises as a key problem in the design of distribution networks. It generalizes both the capacitated facility location problem (CFLP) and the multiple depot vehicle routing problem (MDVRP), the first by considering additional routing decisions and the second by adding the location decision variables. In this thesis we use different mathematical programming tools to develop and specialize new models and algorithms for solving the CLRP. In Chapter 3, three new models are presented for the CLRP based on vehicle-flow and commodity-flow formulations, all of which are shown to dominate, in terms of the linear relaxation lower bound, the original two-index vehicle-flow formulation [19]. Known valid inequalities are complemented with some new ones and included using separation algorithms that in many cases generalize extisting ones found in the literature. Computational experiments suggest that flow models can be efficient for dealing with small or medium size instances of the CLRP (50 customers or less). In Chapter 4, a new branch-and-cut-and-price exact algorithm is introduced for the CLRP based on a set-partitioning formulation. The pricing problem is a shortest path problem with resource constraints (SPPRC). In particular, we consider a relaxation of such problem in which routes are allowed to contain cycles of length three or more. This is complemented with the development of new valid inequalities that are shown to be effective for closing the optimality gap as well as to restrict the appearance of cycles. Computational experience supports the fact that this method is now the best exact method for the CLRP. In Chapter 5, we introduce a new metaheuristic with the aim of finding good quality solutions in short or moderate computing times. First, a bundle of good solutions is generated with the help of a greedy randomized adaptive search procedure (GRASP). Following this, a blending procedure is applied with the aim of producing a better upper bound as a combination of all the others in the bundle. An iterative destroy-and-repair method is then applied using a location-reallocation model that generalizes the reallocation model due to de Franceschi et al. [48].

Depuis une vingtaine d’années, la résolution de problèmes d’optimisation globale non convexes avec contraintes a connu un formidable essor. Les algorithmes de branch and bound basée sur l’analyse d’intervalles ont su trouver leur place, car ils ont l’avantage de prouver l’optimalité de la solution de façon déterministe, avec un niveau de certitude pouvant aller jusqu’à la précision machine. Cependant, la complexité exponentielle en temps et en mémoire de ces algorithmes induit une limite intrinsèque, c’est pourquoi il est toujours nécessaire d’améliorer les techniques actuelles. Dans cette thèse, nous avons développé de nouvelles arithmétiques basées sur l’arithmétique d’intervalles et l’arithmétique affine, afin de calculer des minorants et des majorants de meilleure qualité de fonctions explicites sur un intervalle. Nous avons ensuite développé une nouvelle méthode automatique de construction de relaxations linéaires. Cette construction est basée sur l’arithmétique affine et procède par surcharge des opérateurs. Les programmes linéaires ainsi générés ont exactement le même nombre de variables et de contraintes d’inégalité que les problèmes originaux, les contraintes d’égalité étant remplacées par deux inégalités. Cette nouvelle procédure permet de calculer des minorants fiables et des certificats d’infaisabilité pour chaque sous-domaine à chaque itération de notre algorithme de branch and bound par intervalles. De nombreux tests numériques issus du site COCONUT viennent confirmer l’efficacité de cette approche. Un autre aspect de cette thèse a été l’étude d’une extension de ce type d’algorithmes en introduisant une limite sur mémoire disponible. L’idée principale de cette approche est de proposer un processus inverse de l’optimisation par le biais d’un principe métaheuristique : plutôt que d’améliorer des solutions locales à l’aide de métaheuristiques telles que les algorithmes Taboo ou VNS, nous partons d’une méthode exacte et nous la modifions en une heuristique. De cette façon, la qualité de la solution trouvée peut être évaluée. Une étude de la complexité de ce principe métaheuristique a également été effectuée. Enfin, pour finir l’étude, nous avons appliqué notre algorithme à la résolution de problème en géométrie plane, ainsi qu’à la résolution d’un problème de dimensionnement de moteur électrique. Les résultats obtenus ont permis de confirmer l’intérêt de ce type d’algorithme, en résolvant des problèmes ouverts sur les polygones convexes et proposant des structures innovantes en génie électrique. / Since about thirty years, interval Branch and Bound algorithms are increasingly used to solve constrained global optimization problems in a deterministic way. Such algorithms are reliable, i.e., they provide an optimal solution and its value with guaranteed bounds on the error, or a proof that the problem under study is infeasible. Other approaches to global optimization, while useful and often less time-consuming than interval methods, do not provide such a guarantee. However, the exponential complexity in time and memory of interval Branch and Bound algorithms implies a limitation, so it is always necessary to improve these methods. In this thesis, we have developed new arithmetics based on interval arithmetic and affine arithmetic, to compute better lower and upper bounds of a factorable function over an interval. An automatic method for constructing linear relaxations of constrained global optimization problems is proposed. Such a construction is based on affine and interval arithmetics and uses operator overloading. These linear programs have exactly the same numbers of variables and of inequality constraints as the given problems. Each equality constraint is replaced by two inequalities. This new procedure for computing reliable bounds and certificates of infeasibility is inserted into a classical interval Branch and Bound algorithm. Extensive computation experiments, made on a sample of test problems from the COCONUT database, prove its effectiveness. Another aspect is the study of an extension of such a global optimization code by limiting the available memory. The main idea of this new kind of metaheuristique is to propose a reverse process of optimization via heuristics : rather than improving local solutions by using metaheuristics such as Taboo or VNS, we begin with an exact method and we modify it into a heuristic one. In such a way, the quality of the solution could be evaluated. Moreover, a study of the complexity of this metaheurisque has been done. Finally, we applied our algorithm to solve open problem in geometry, and to solve a design problem of an electric motor. The results have confirmed the usefulness of this kind of algorithms, solving open problems on convex polygons and offering innovative structures in electrical engineering.

La survie des réseaux est un domaine d'étude technique très intéressant ainsi qu'une préoccupation critique dans la conception des réseaux. Compte tenu du fait que de plus en plus de données sont transportées à travers des réseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des réseaux consistent à fournir une capacité supplémentaire dans un réseau et à réacheminer les flux automatiquement autour de la panne en utilisant cette disponibilité de capacité. Cette thèse porte sur la conception de réseaux optiques intégrant des techniques de survie qui utilisent des schémas de protection basés sur les p-cycles. Plus précisément, les p-cycles de protection par chemin sont exploités dans le contexte de pannes sur les liens. Notre étude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opération pour l'ensemble des requêtes sont définis a priori. La majorité des travaux existants utilisent des heuristiques ou des méthodes de résolution ayant de la difficulté à résoudre des instances de grande taille. L'objectif de cette thèse est double. D'une part, nous proposons des modèles et des méthodes de résolution capables d'aborder des problèmes de plus grande taille que ceux déjà présentés dans la littérature. D'autre part, grâce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de génération de colonnes, celle-ci étant adéquate pour résoudre des problèmes de programmation linéaire de grande taille. Dans ce projet, la génération de colonnes est utilisée comme une façon intelligente d'énumérer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problème maître et le problème auxiliaire ainsi qu'un premier algorithme de génération de colonnes pour la conception de réseaux protegées par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les méthodes existantes. Par la suite, une formulation plus compacte est proposée pour le problème auxiliaire. De plus, nous présentons une nouvelle méthode de décomposition hiérarchique qui apporte une grande amélioration de l'efficacité globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux méthodes heurisiques qui arrivent à trouver des bonnes solutions. Nous nous attardons aussi à une comparaison systématique entre les p-cycles et les schémas classiques de protection partagée. Nous effectuons donc une comparaison précise en utilisant des formulations unifiées et basées sur la génération de colonnes pour obtenir des résultats de bonne qualité. Par la suite, nous évaluons empiriquement les versions orientée et non-orientée des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scénarios de trafic asymétrique. Nous montrons quel est le coût de protection additionnel engendré lorsque des systèmes bidirectionnels sont employés dans de tels scénarios. Finalement, nous étudions une formulation de génération de colonnes pour la conception de réseaux avec des p-cycles en présence d'exigences de disponibilité et nous obtenons des premières bornes inférieures pour ce problème. / Network survivability is a very interesting area of technical study and a critical concern in network design. As more and more data are carried over communication networks, a single outage can disrupt millions of users and result in millions of dollars of lost revenue. Survivability techniques involve providing some redundant capacity within the network and automatically rerouting traffic around the failure using this redundant capacity. This thesis concerns the design of survivable optical networks using p-cycle based schemes, more particularly, path-protecting p-cycles, in link failure scenarios. Our study focuses on the placement of p-cycle protection structures assuming that the working routes for the set of connection requests are defined a priori. Most existing work carried out on p-cycles concerns heuristic algorithms or methods suffering from critical lack of scalability. Thus, the objective of this thesis is twofold: on the one hand, to propose scalable models and solution methods enabling to approach larger problem instances and on the other hand, to produce optimal or near optimal solutions with mathematically proven optimality gaps. For this, we rely on the column generation technique which is suitable to solve large scale linear programming problems. Here, column generation is used as an intelligent way of implicitly enumerating promising cycles to be part of p-cycle designs. At first, we propose mathematical formulations for the master and the pricing problems as well as the first column generation algorithm for the design of survivable networks based on path-protecting p-cycles. The resulting algorithm obtains better solutions within reasonable running time in comparison with existing methods. Then, a much more compact formulation of the pricing problem is obtained. In addition, we also propose a new hierarchical decomposition method which greatly improves the efficiency of the whole algorithm and allows us to solve larger problem instances. As for integer solutions, two heuristic approaches are proposed to obtain good solutions. Next, we dedicate our attention to a systematic comparison of p-cycles and classical shared protection schemes. We perform an accurate comparison by using a unified column generation framework to find provably good results. Afterwards, our study concerns an empirical evaluation of directed and undirected link- and path-protecting p-cycles under asymmetric traffic scenarios. We show how much additional protection cost results from employing bidirectional systems in such scenarios. Finally, we investigate a column generation formulation for the design of p-cycle networks under availability requirements and obtain the first lower bounds for the problem.

Thèse réalisée en cotutelle avec l'Université d'Avignon. / Les problèmes d’optimisation discrète sont pour beaucoup difficiles à résoudre, de par leur nature combinatoire. Citons par exemple les problèmes de programmation linéaire en nombres entiers. Une approche couramment employée pour les résoudre exactement est l’approche de Séparation et Évaluation Progressive. Une approche différente appelée « Resolution Search » a été proposée par Chvátal en 1997 pour résoudre exactement des problèmes d’optimisation à variables 0-1, mais elle reste mal connue et n’a été que peu appliquée depuis. Cette thèse tente de remédier à cela, avec un succès partiel. Une première contribution consiste en la généralisation de Resolution Search à tout problème d’optimisation discrète, tout en introduisant de nouveaux concepts et définitions. Ensuite, afin de confirmer l’intérêt de cette approche, nous avons essayé de l’appliquer en pratique pour résoudre efficacement des problèmes bien connus. Bien que notre recherche n’ait pas abouti sur ce point, elle nous a amené à de nouvelles méthodes pour résoudre exactement les problèmes d’affectation généralisée et de localisation simple. Après avoir présenté ces méthodes, la thèse conclut avec un bilan et des perspectives sur l’application pratique de Resolution Search. / The combinatorial nature of discrete optimization problems often makes them diffi- cult to solve. Consider for instance integer linear programming problems, which are commonly solved using a Branch-and-Bound approach. An alternative approach, Resolution Search, was proposed by Chvátal in 1997 for solving 0-1 optimization problems, but remains little known to this day and as such has seen few practical applications. This thesis attempts to remedy this state of affairs, with partial success. Its first contribution consists in the generalization of Resolution Search to any discrete optimization problem, while introducing new definitions and concepts. Next, we tried to validate this approach by attempting to solve well-known problems efficiently with it. Although our research did not succeed in this respect, it lead us to new methods for solving the generalized assignment and uncapacitated facility location problems. After presenting these methods, this thesis concludes with a summary of our attempts at practical application of Resolution Search, along with further perspectives on this matter.

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.

Dans des contextes de post-urgence tels que le vit la partie occidentale de la République Démocratique du Congo (RDC), l’un des défis cruciaux auxquels font face les hôpitaux ruraux est de maintenir un niveau de médicaments essentiels dans la pharmacie. Sans ces médicaments pour traiter les maladies graves, l’impact sur la santé de la population est significatif. Les hôpitaux encourent également des pertes financières dues à la péremption lorsque trop de médicaments sont commandés. De plus, les coûts du transport des médicaments ainsi que du superviseur sont très élevés pour les hôpitaux isolés ; les coûts du transport peuvent à eux seuls dépasser ceux des médicaments. En utilisant la province du Bandundu, RDC pour une étude de cas, notre recherche tente de déterminer la faisabilité (en termes et de la complexité du problème et des économies potentielles) d’un problème de routage synchronisé pour la livraison de médicaments et pour les visites de supervision. Nous proposons une formulation du problème de tournées de véhicules avec capacité limitée qui gère plusieurs exigences nouvelles, soit la synchronisation des activités, la préséance et deux fréquences d’activités. Nous mettons en œuvre une heuristique « cluster first, route second » avec une base de données géospatiales qui permet de résoudre le problème. Nous présentons également un outil Internet qui permet de visualiser les solutions sur des cartes. Les résultats préliminaires de notre étude suggèrent qu’une solution synchronisée pourrait offrir la possibilité aux hôpitaux ruraux d’augmenter l’accessibilité des services médicaux aux populations rurales avec une augmentation modique du coût de transport actuel. / In post-emergency contexts such as in Western Democratic Republic of the Congo, also known as DR Congo, one of the crucial challenges that rural hospitals face is maintaining a pharmacy with essential medications and supplies. There is significant negative humanitarian impact when hospitals do not have essential medications for treatable life-threatening diseases; hospitals also incur financial losses when too much medication is ordered and it expires. Moreover, the cost of transporting medications and providing onsite supervision to remote hospitals is an extremely expensive endeavour. In some cases the transportation costs alone can surpass the cost of the medications. Using the province of Bandundu, DR Congo as a case study, we attempt to determine the feasibility (in terms of both problem complexity and potential savings) of a synchronized routing problem for medication delivery and on-site supervision visits. We propose a Capacitated Vehicle Routing Problem formulation that handles several novel requirements including activity-wise synchronization, precedence, and two activity frequencies. We implement a novel cluster-first, route-second heuristic with a geospatially-enabled database to solve the problem. We also present a Web-based tool to visualize the solutions in a map. The preliminary results of the research suggest that a synchronized solution could allow rural hospitals to increase the accessibility of medical services to rural populations with only a modest increase in transportation costs.

Les métaheuristiques sont très utilisées dans le domaine de l'optimisation discrète. Elles permettent d’obtenir une solution de bonne qualité en un temps raisonnable, pour des problèmes qui sont de grande taille, complexes, et difficiles à résoudre. Souvent, les métaheuristiques ont beaucoup de paramètres que l’utilisateur doit ajuster manuellement pour un problème donné. L'objectif d'une métaheuristique adaptative est de permettre l'ajustement automatique de certains paramètres par la méthode, en se basant sur l’instance à résoudre. La métaheuristique adaptative, en utilisant les connaissances préalables dans la compréhension du problème, des notions de l'apprentissage machine et des domaines associés, crée une méthode plus générale et automatique pour résoudre des problèmes. L’optimisation globale des complexes miniers vise à établir les mouvements des matériaux dans les mines et les flux de traitement afin de maximiser la valeur économique du système. Souvent, en raison du grand nombre de variables entières dans le modèle, de la présence de contraintes complexes et de contraintes non-linéaires, il devient prohibitif de résoudre ces modèles en utilisant les optimiseurs disponibles dans l’industrie. Par conséquent, les métaheuristiques sont souvent utilisées pour l’optimisation de complexes miniers. Ce mémoire améliore un procédé de recuit simulé développé par Goodfellow & Dimitrakopoulos (2016) pour l’optimisation stochastique des complexes miniers stochastiques. La méthode développée par les auteurs nécessite beaucoup de paramètres pour fonctionner. Un de ceux-ci est de savoir comment la méthode de recuit simulé cherche dans le voisinage local de solutions. Ce mémoire implémente une méthode adaptative de recherche dans le voisinage pour améliorer la qualité d'une solution. Les résultats numériques montrent une augmentation jusqu'à 10% de la valeur de la fonction économique. / Metaheuristics are a useful tool within the field of discrete optimization that allow for large, complex, and difficult optimization problems to achieve a solution with a good quality in a reasonable amount of time. Often metaheuristics have many parameters that require a user to manually define and tune for a given problem. An adaptive metaheuristic aims to remove some parameters from being tuned or defined by the end user by allowing the method to specify and/or adapt a parameter or set of parameters based on the problem. The adaptive metaheuristic, using advancements in understanding of the problem being solved, machine learning, and related fields, aims to provide this more generalized and automatic toolkit for solving problems. Global optimization of mining complexes aims to schedule material movement in mines and processing streams to maximize the economic value of the system. Often due to the large number of integer variables within the model, complicated constraints, and non-linear constraints, it becomes prohibitive to solve these models using commercially available optimizers. Therefore, metaheuristics are often employed in solving mining complexes. This thesis builds upon a simulated annealing method developed by Goodfellow & Dimitrakopoulos (2016) to optimize the stochastic global mining complex. The method outlined by the authors requires many parameters to be defined to operate. One of these is how the simulated annealing algorithm searches the local neighborhood of solutions. This thesis illustrates and implements an adaptive way of searching the neighborhood for increasing the quality of a solution. Numerical results show up to a 10% increase in objective function value.