The master’s thesis focuses on the optimization models in logistics with emphasis on the network interdiction problem. The brief introduction is followed by two overview chapters - graph theory and mathematical programming. Important definitions strongly related to network interdiction problems are introduced in the chapter named Basic concepts of graph theory. Necessary theorems used for solving problems are following the definitions. Next chapter named Introduction to mathematical programming firstly contains concepts from linear programming. Definitions and theorems are chosen with respect to the following maximum flow problem and the derived dual problem. Concepts of stochastic optimization follow. In the fifth chapter, we discuss deterministic models of the network interdiction. Stochastic models of the network interdiction follow in the next chapter. All models are implemented in programmes written in the programming language GAMS, the codes are attached.

Garg and Könemann developed a framework for computing multi-commodity maximum flow in a graph, later called a multiplicative weight update framework. Madry used this framework and exchanged Dijkstra’s algorithm to a dynamic graph algorithm for approximating the shortest paths through the graph. With this approachhe developed the fastest algorithm to date for calculating the multi-commodity maximum flow, with a running time of Õ(mnϵ2). This project have implemented the algorithm and compared it with a slightly modified version of the former fastest algorithm by Fleischer with a time complexity of Õ(m2ϵ2). The results show that Madry’s algorithms is slower than Fleischer’s algorithm in practice for graph with less than 100 million edges. This project also computed the space needed for the dynamic algorithms used in Madry’s algorithm and can show a resulting space complexity of O(n(n+m)log2n), compared to the space complexity of Fleischer’s algorithm of O(n). For a graph with 100 million edges, 50 million Gb of space is needed to use Madry’s algorithm, which is more than our test computers had. We can therefore conclude that Madry’s algorithm is not usable in real life today, both in terms of memory usage and time consumption. / Garg and Könemann utvecklade ett framework för att beräkna multi-commodity maximum flöde i en graf sedan kallat ett multiplicative weight update framework. Madry använde detta framework och bytte ut Dijkstra’s algoritm mot en dynamisk grafalgoritm för att kunna approximera kortaste vägen i grafen. Med detta angeppssätt utvecklade han den idag snabbaste algoritmen för beräkning av multicommodity maximum flöde med en tids komplexitet på Õ(mnϵ2). Det här projektet har implementerat hans algoritm och jämfört den med den tidigare snabbaste algoritmen skapad av Fleischer med en tidskomplexitet på Õ(m2ϵ2). Resultatet visar att Madrys algoritm är långsammare än Fleischers algoritm i praktiken för grafer med färre än 100 miljoner kanter. Detta projekt beräknade också minnesåtgången för de dynamiska algoritmerna i Madrys algorithm och kan visa en resulterade minneskomplexitet på O(n(n+m)log2n), jämfört med Fleischers algoritm på O(n). För en graf med 100 miljoner kanter så behövs 50 miljoner Gb av minne för att kunna använda Madrys algoritm, vilket var mer än våra testdatorer hade. Vi kan därför konstatera att Madrys algoritm inte är användbar i praktiken idag, både när det kommer till minnesanvändning och till tidsåtgång.

Dans les chaînes d’approvisionnement, les producteurs font souvent appel à des entreprises de transport pour livrer leurs marchandises. Cela peut entraîner une concurrence entre les transporteurs qui cherchent à maximiser leurs revenus individuels en desservant un produc- teur. Dans ce travail, nous considérons de telles situations où aucun transporteur ne peut garantir la livraison de la source à la destination en raison de son activité dans une région restreinte (par exemple, une province) ou de la flotte de transport disponible (par exemple, uniquement le transport aérien), pour ne citer que quelques exemples. La concurrence est donc liée à l’expansion de la capacité de transport des transporteurs. Le problème décrit ci-dessus motive l’étude du jeu d’expansion de réseau multi-agent joué sur un réseau appartenant à de multiples transporteurs qui choisissent la capacité de leurs arcs. Simultanément, un client cherche à maximiser le flux qui passe par le réseau en décidant de la politique de partage qui récompense chacun des transporteurs. Le but est de déterminer un équilibre de Nash pour le jeu, en d’autres termes, la strategie d’extension de capacité et de partage la plus rationnelle pour les transporteurs et le client, respectivement. Nous rappelons la formulation basée sur les arcs proposée dans la littérature, dont la solution est l’équilibre de Nash avec le plus grand flux, et nous identifions ses limites. Ensuite, nous formalisons le concept de chemin profitable croissant et nous montrons son utilisation pour établir les conditions nécessaires et suffisantes pour qu’un vecteur de stratégies soit un équilibre de Nash. Ceci nous conduit à la nouvelle formulation basée sur le chemin. Enfin, nous proposons un renforcement du modèle basé sur les arcs et une formulation hybride arc- chemin. Nos résultats expérimentaux soutiennent la valeur des nouvelles inégalités valides obtenues à partir de notre caractérisation des équilibres de Nash avec des chemins croissants rentables. Nous concluons ce travail avec les futures directions de recherche pavées par les contributions de cette thèse. / In supply chains, manufacturers often use transportation companies to deliver their goods. This can lead to competition among carriers seeking to maximize their individual revenues by serving a manufacturer. In this work, we consider such situations where no single carrier can guarantee delivery from source to destination due to its operation in a restricted region (e.g., a province) or the available transportation fleet (e.g., only air transportation), to name a few examples. Therefore, competition is linked to the expansion of transportation capacity by carriers. The problem described above motivates the study of the multi-agent network expansion game played over a network owned by multiple transporters who choose their arcs’ capacity. Simultaneously, a customer seeks to maximize the flow that goes through the network by deciding the sharing policy rewarding each of the transporters. The goal is to determine a Nash equilibrium for the game, in simple words, the most rational capacity expansion and sharing policy for the transporters and the customer, respectively. We recap the arc-based formulation proposed in literature, whose solution is the Nash equilibirum with the largest flow, and we identify its limitations. Then, we formalize the concept of profitable increasing path and we show its use to establish necessary and sufficient conditions for a vector of strategies to be a Nash equilibrium. This lead us to the first path-based formulation. Finally, we propose a strengthening for the arc-based model and a hybrid arc-path formulation. Our experimental results support the value of the new valid inequalities obtained from our characterization of Nash equilibria with profitable increasing paths. We conclude this work with the future research directions paved by the contributions of this thesis.