This article studies the linear multicommodity network flow problem. This kind of problem arises in a wide variety of contexts. A numerical implementation of the primal-dual interior-point method is designed to solve the problem. In the interior-point method, at each iteration, the corresponding linear system, expressed as a normal equations system, is solved by using the AINV algorithm combined with a preconditioned conjugate gradient algorithm or by the AINV algorithm for the whole normal equations. Numerical experiments are conducted for networks of different dimensions and numbers of products for the distribution problem. The computational results show the effectiveness of the interior-point method for this class of network problems.

We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all arc latency functions are linear and there is a single source and sink. Still, one can prove that an optimal flow and an equilibrium flow share a desirable property in this situation: all flow-carrying paths have the same length; i.e., these solutions are "fair," which is in general not true for the optimal flow in networks with nonlinear latency functions. In addition, the maximum latency of the Nash equilibrium, which can be computed efficiently, is within a constant factor of that of an optimal solution. That is, the so-called price of anarchy is bounded. In contrast, we present a family of instances that shows that the price of anarchy is unbounded for instances with multiple sources and a single sink, even in networks with linear latencies. Finally, we show that an s-t-flow that is optimal with respect to the average latency objective is near optimal for the maximum latency objective, and it is close to being fair. Conversely, the average latency of a flow minimizing the maximum latency is also within a constant factor of that of a flow minimizing the average latenc

abstract: This thesis addresses the following fundamental maximum throughput routing problem: Given an arbitrary edge-capacitated n-node directed network and a set of k commodities, with source-destination pairs (s_i,t_i) and demands d_i> 0, admit and route the largest possible number of commodities -- i.e., the maximum throughput -- to satisfy their demands. The main contributions of this thesis are three-fold: First, a bi-criteria approximation algorithm is presented for this all-or-nothing multicommodity flow (ANF) problem. This algorithm is the first to achieve a constant approximation of the maximum throughput with an edge capacity violation ratio that is at most logarithmic in n, with high probability. The approach used is based on a version of randomized rounding that keeps splittable flows, rather than approximating those via a non-splittable path for each commodity: This allows it to work for arbitrary directed edge-capacitated graphs, unlike most of the prior work on the ANF problem. The algorithm also works if a weighted throughput is considered, where the benefit gained by fully satisfying the demand for commodity i is determined by a given weight w_i>0. Second, a derandomization of the algorithm is presented that maintains the same approximation bounds, using novel pessimistic estimators for Bernstein's inequality. In addition, it is shown how the framework can be adapted to achieve a polylogarithmic fraction of the maximum throughput while maintaining a constant edge capacity violation, if the network capacity is large enough. Lastly, one important aspect of the randomized and derandomized algorithms is their simplicity, which lends to efficient implementations in practice. The implementations of both randomized rounding and derandomized algorithms for the ANF problem are presented and show their efficiency in practice. / Dissertation/Thesis / Masters Thesis Computer Science 2020

[pt] Problemas de multifluxos surgem como modelos básicos no contexto de várias aplicações de fluxos em redes, tais como redes de telecomunicações, redes de transporte e logística. Em tais aplicações, os fluxos que atravessam a rede compartilham simultaneamente os mesmos recursos disponíveis e são definidos por suas próprias restrições. A cada uma das arestas ligando os pontos da rede está associado um custo, fixo ou proporcional à sua utilização. Este trabalho trata problemas de projeto de redes multifluxos, em que os custos estão associados às capacidades instaladas nas arestas. Particularmente, será estudado o caso em que a função de custo nas arestas possui o comportamento de uma função escada crescente e descontínua, para o qual métodos exatos de resolução são ineficientes. Métodos heurísticos são propostos para a resolução aproximada do problema e sintetizados em um algoritmo de multi-partida com memória adaptativa. Um mecanismo de intensificação, conhecido na literatura como construção de vocabulário, é também explorado e aplicado. Finalmente, experimentos computacionais são realizados e o método de resolução proposto é analisado quanto aos seus resultados e os resultados obtidos pelo método de resolução proposto são analisados. O método obtém as melhores soluções conhecidas para algumas instâncias da literatura. / [en] Multicommodity flow problems arise widely as basic models in the context of network flows applications such as telecommunication networks, transportation problems, and logistic. In these applicatons, the flows that cross the networks share the same avaiable resources simultaneously and are defined by their own constraints. Each edge connecting two nodes in the network has an associated cost that is either fixed or proportional to its use. This work focuses on a network design problem in which the cost are associated with the capacities installed in the edges. Particularly, the network design problem studied has discrete and step increasing cost functions on the edges, for which exact methods are inefficient. Heuristics are proposed for the approximate memory algorithm. An intensification mechanism, known in the literature as vocabulary building, is also explored and applied. Finally, computational experiments are performed and the results obtained with the proposed solution method are evaluated. The method obtains the best known solutions for some instances in the literature.

Dans les réseaux de télécommunications, la demande croissante pour de nouveaux services, comme la diffusion de vidéos en continu ou les conférences en ligne, engendre un besoin pour des dispositifs de télécommunication où le même contenu est acheminé depuis un émetteur unique vers un groupe de récepteurs. Cette évolution ouvre la voie au développement de nouvelles techniques d'acheminement des données, comme le multicast qui laisse un nœud du réseau copier ses données d'entrée puis retransmettre ces copies, ou le codage réseau, qui est une technique permettant à un nœud d'effectuer des opérations de codage à partir de ses données d'entrée. Cette thèse traite de la mise en place de techniques de codage au sein d'un réseau multicast filaire. Nous formalisons certains problèmes qui apparaissent naturellement dans ce contexte grâce à la recherche opérationnelle et à des outils d'optimisation mathématique. Notre objectif est de développer des modèles et des algorithmes afin de calculer, au moins de manière approchée, certaines grandeurs qui ont vocation à être pertinentes dans le cadre de la comparaison de techniques d'acheminement de données dans un réseau de télécommunications. Nous évaluons ainsi, d'un point de vue à la fois théorique et expérimental, l'impact induit par l'introduction de techniques de codage au sein d'un réseau multicast. Nous nous concentrons en particulier sur des critères importants pour un opérateur de télécommunication, comme la maximisation du débit d'information entre une source et un ensemble de destinataires dans le réseau, la minimisation de la congestion sous contrainte de demande, ou la minimisation de la perte de débit ou du coût induit par l'acheminement des données dans un réseau soumis à des pannes. / In telecommunication networks, the increasing demand for new services, like video-streaming or teleconferencing, along with the now common situation where the same content is simultaneously requested by a huge number of users, stress the need for point to many data transmission protocols where one sender wishes to transmit the same data to a set of receivers. This evolution leads to the development of new routing techniques like multicast, where any node of the network can copy its received data and then send these copies, or network coding, which is a technique allowing any node to perform coding operations on its data. This thesis deals with the implementation of coding techniques in a wired multicast network. We formalize some problems naturally arising in this setting by using operations research and mathematical optimization tools. Our objective is to develop models and algorithms which could compute, at least approximately, some quantities whose purpose is to be relevant as far as forwarding data using either multicast and network coding in telecommunications networks is concerned. We hence evaluate, both in theory and numerically, the impact of introducing coding techniques in a multicast network. We specifically investigate relevant criteria, with respect to the field of telecommunications, like the maximum amount of information one can expect to convey from a source to a set of receivers through the network, the minimum congestion one can guarantee while satisfying a given demand, or the minimum loss in throughput or cost induced by a survivable routing in a network prone to failures.