We study the existence of flows in infinite networks and extend basic theorems due to Gale and Hoffman and to Ford and Fulkerson. The classical approach to finite networks uses a constructive combinatorical algorithm that has become known as the labelling algorithm. Our approach to infinite networks involves Hahn--Banach type theorems on the existence of certain linear functionals. Thus the main tools are from the theory of functional and convex analysis. In Chapter II, we discuss sublinear and linear functionals on real vector spaces in the spirit of the work of K"{o}nig. In particular, a generalization of K"{o}nig's minimum theorem is established. Our theory leads to some useful interpolation results. We also establish a variant of the main interpolation theorem in the context of convex cones. We reformulate the results of Ford--Fulkerson and Gale--Hoffman in terms of certain additive and biadditive set functions. In Chapter III, we show that the space of all additive set functions may be canonically identified with the dual space of a space of certain step functions and that the space of all biadditive set functions may be identified with the dual space of a space of certain step functions in two variables. Our work an additive set functions is in the spirit of classical measure theory, while the case of biadditive set functions resembles the theory of product measures. In Chapter IV, we develop an extended version of the Gale--Hoffman theorem on the existence of flows in infinite networks in a setting of measure-theoretic flavor. This general flow theorem is one of our central results. We discuss, as an application of our flow theorem, a Ford--Fulkerson type result on maximal flows and minimal cuts in infinite networks containing sources and sinks. In addition, we present applications to flows in locally finite networks and to the existence of antisymmetric flows under certain natural conditions. We conclude with a discussion of the case of triadditive set functions. In the appendix, we review briefly the classical theory of maximal flows and minimal cuts in networks with finitely many nodes.

No description available.

We present a faster implementation of the polynomial time primal simplex algorithm due to Orlin [23]. His algorithm requires O(nm min{log(nC), m log n}) pivots and O(n2 m ??n{log nC, m log n}) time. The bottleneck operations in his algorithm are performing the relabeling operations on nodes, selecting entering arcs for pivots, and performing the pivots. We show how to speed up these operations so as to yield an algorithm whose running time is O(nm. log n) per scaling phase. We show how to extend the dynamic-tree data-structure in order to implement these algorithms. The extension may possibly have other applications as well.

Integer multicommodity network flow (MCNF) models have applications in various areas like logistics, freight transportation, telecommunication and manufacturing. In this thesis we study an extension of the integer MCNF problem (MCNF-FIFO) where commodities are handled (processed) in a first-in-first-out (FIFO) order at each transshipment location and resource capacities are shared across arcs in the network. The objective of the MCNF-FIFO model is to find feasible routes for all commodities from their origins to destinations while minimizing the total transportation and holding cost or the sum of delivery times. We formulate the MCNF-FIFO problem on a time-space network and develop three different integer-programming (IP) formulations for the FIFO constraints, and two IP formulations for the flow conservations requirements. Since these formulations have a very large number of variables and constraints, we develop various algorithmic strategies to obtain good quality solutions quickly. The first strategy is to reduce the problem size by using properties of the optimal solution. We develop novel problem reduction and decomposition techniques that eliminate variables and constraints, and decompose the problem into smaller components. To further reduce the problem size, we classify the FIFO constraints into different categories by utilizing the relationships between different commodities, and provide specialized formulations for each of these categories so as to reduce the number of FIFO constraints significantly. The second strategy is to develop heuristic algorithms that provide near-optimal solutions to the MCNF-FIFO problem. Our first algorithm is an optimization-based heuristic that solves a relaxed MCNF-FIFO model with a limited number of FIFO constraints. Then, it removes the remaining infeasibilities in the solution of the relaxed MCNF-FIFO model using a repair heuristic to obtain a feasible solution. We develop two other heuristic algorithms that are stand-alone construction heuristics that build a feasible solution from scratch. To assess the effectiveness of the modeling and algorithmic enhancements, we implement the methods and apply them to three real life test instances. Our tests show that the problem reduction techniques are very effective in reducing the solution times. Among the heuristic algorithms, the optimization-based heuristic performs the best to find near-optimal solutions quickly. / text

Botnets are becoming the predominant threat on the Internet today and is the primary vector for carrying out attacks against organizations and individuals. Botnets have been used in a variety of cybercrime, from click-fraud to DDOS attacks to the generation of spam. In this thesis we propose an approach to detect botnet activity using two different strategies both based on machine learning techniques. In one, we examine the network flow based metrics of potential botnet traffic and show that we are able to detect botnets with only data from a small time interval of operation. For our second technique, we use a similar strategy to identify botnets based on their potential fast flux behavior. For both techniques, we show experimentally that the presence of botnets may be detected with a high accuracy and identify their potential limitations. / Graduate

A typical problem in traffic control is the steering over a network of vehicles with different origins and destinations. In this report this scenario is formulated as a multi-commodity network flow problem, a linear programming problem whose objective is to transport, with minimum cost, different commodities from their respective sources to their sinks through a network, while respecting the capacity constraints of the roads. The dynamic network flow formulation of the problem is also presented, extending the network over time to incorporate the temporal dimension. Different algorithms for solving the multi-commodity network flow problem are examined. First, the simplex method, more precisely its revised version, is considered, and then the Dantzig-Wolfe decomposition is illustrated, an optimization algorithm which exploits specific block structures in the constraints. These methods are applied using state-of-the-art linear programming solvers and evaluated with a simulation based on the road network in central Stockholm. The results show that both methods allow for solving the traffic flow problem, with limitations given by the specifics of the solvers and by the space and time discretization of the problem. In particular, the revised simplex algorithm results the faster method.

In the oil industry, there is a special class of pipelines used for the transportation of refined products. The problem of sequencing the inputs to be pumped through this type of pipeline seeks to generate the optimal sequence of batches of products and their destination as well as the amount of product to be pumped such that the total operational cost of the system, or another operational objective, is optimized while satisfying the product demands according to the requirements set by the customers. This dissertation introduces a new modeling approach and proposes a solution methodology for this problem capable of dealing with the topology of all the scenarios reported in the literature so far. The system representation is based on a 1-0 multi commodity network flow formulation that models the dynamics of the system, including aspects such as conservation of product flow constraints at the depots, travel time of products from the refinery to their depot destination and what happens upstream and downstream the line whenever a product is being received at a given depot while another one is being injected into the line at the refinery. It is assumed that the products are already available at the refinery and their demand at each depot is deterministic and known beforehand. The model provides the sequence, the amounts, the destination and the trazability of the shipped batches of different products from their sources to their destinations during the entire horizon planning period while seeking the optimization of pumping and inventory holding costs satisfying the time window constraints. A survey for the available literature is presented. Given the problem structure, a decomposition based solution procedure is explored with the intention of exploiting the network structure using the network simplex method. A branch and bound algorithm that exploits the dynamics of the system assigning priorities for branching to a selected set of variables is proposed and its computational results for the solution, obtained via GAMS/CPLEX, of the formulation for random instances of the problem of different sizes are presented. Future research directions on this field are proposed.

This dissertation proposes approaches that enable effective planning and control of mobile transportation resources in large-scale consolidation networks. We develop models, algorithms, and methodologies that are applied to fleet sizing and fleet repositioning. Three specific but interrelated problems are studied. The first two relate to the trade-offs between fleet size and repositioning costs in transportation resource management, while the third involves a dynamic empty repositioning problem with explicit consideration of the uncertainty of future requirements that will be revealed over time. Chapter 1 provides an overview of freight trucking, including the consolidation trucking systems that will be the focus of this research. Chapter 2 proposes an optimization modeling approach for analyzing the trade-off between the cost of a larger fleet of tractors and the cost of repositioning tractors for a trucking company operating a consolidation network, such as a less-than-truckload (LTL) company. Specifically, we analyze the value of using extra tractor repositioning moves (in addition to the ones required to balance resources throughout the network) to attain savings in the fixed costs of owning or leasing a tractor fleet during a planning horizon. The primary contributions of the research in this chapter are that (1) we develop the first optimization models that explore the impact of fleet size reductions via repositioning strategies that have regularity and repeatability properties, and (2) we demonstrate that substantial savings in operational costs can be achieved by repositioning tractors in anticipation of regional changes in freight demand. Chapter 3 studies the optimal Pareto frontiers between the fleet size and repositioning costs of resources required to perform a fixed aperiodic or periodic schedule of transportation requests. We model resource schedules in two alternative ways: as flows on event-based, time-expanded networks; and as perfect matchings on bipartite networks. The main contributions from this chapter are that (1) we develop an efficient re-optimization procedure to compute adjacent Pareto points that significantly reduces the time to compute the entire Pareto frontier of fleet size versus repositioning costs in aperiodic networks, (2) we show that the natural extension to compute adjacent Pareto points in periodic networks does not work in general as it may increase the fleet size by more than one unit, and (3) we demonstrate that the perfect matching modeling framework is frequently intractable for large-scale instances. Chapter 4 considers robust models for dynamic empty-trailer repositioning problems in very large-scale consolidation networks. We investigate approaches that deploy two-stage robust optimization models in a rolling horizon framework to address a multistage dynamic empty repositioning problem in which information is revealed over time. Using real data from a national package/parcel express carrier, we develop and use a simulation to evaluate the performance of repositioning plans in terms of unmet loaded requests and execution costs. The main contributions from this chapter are that (1) we develop approaches for embedding two-stage robust optimization models within a rolling horizon framework for dynamic empty repositioning, (2) we demonstrate that such approaches enable the solution of very large-scale instances, and (3) we show that less conservative implementations of robust optimization models are required within rolling horizon frameworks. Finally, Chapter 5 summarizes the main conclusions from this dissertation and discusses directions for further research.

[pt] A Cerveja Heineken está presente em onze países da América Latina. Alguns têm sua demanda suprida por plantas industriais localizadas no próprio território, outros pela importação a partir de plantas localizadas em outros países da região e ainda há aqueles que dependem do fornecimento de cerveja da matriz da empresa localizada na Holanda. Considerando os mercados latino-americanos que são supridos regularmente por plantas industriais localizadas no exterior, apresentam-se três fornecedores (sources) distintos: Holanda, Argentina e Chile. Motivada pelo grande volume de cerveja importado da Heineken Holanda, pelos custos gerados por estas importações e ainda pelos problemas ocasionados pela dificuldade de algumas plantas cervejeiras locais em atender a demanda externa – entende-se por locais aquelas localizadas na região da América Latina -, esta dissertação se desenvolve. Assim, o intuito desse estudo é analisar a dinâmica da rede de distribuição de Cerveja Heineken para os países da América Latina, com vistas a identificar potenciais novas bases e propor uma melhor organização do fluxo de exportação. O objetivo é otimizar esse fluxo, reduzindo custos através da regionalização das chamadas sources, que nada mais são do que as plantas industriais cervejeiras que exportam e suprem os diversos países latinoamericanos. Para atender a este propósito, serão testadas potenciais sources e avaliados, por meio de ferramentas logísticas, os cenários que poderão suprir de forma mais eficaz os mercados da região. / [en] The Heineken Beer is present in eleven Latin-American countries. Some of them have their demand supplied by breweries located in their own countries, others by the importation from breweries located in other countries of the region and there are still those that depend on the beer exported from the headquarters of the company, in The Netherlands. Considering the Latin-American markets that have their demand regularly supplied by breweries located abroad, we identify three different origins: Holland, Argentina and Chile. Motivated by the large volume of beer imported from Heineken in The Netherlands, by the costs generated by such importations and also by the problems brought about by the difficulties found by some local breweries in order to meet their foreign demand - by local I mean located in the region of Latin America -, this dissertation is developed. The aim of this study is to analyze the dynamics of the distribution network of Heineken Beer throughout Latin-America, in order to identify potential new export bases and propose a better organization of the export flow. The objective is to optimize such flow, reducing costs through the regionalization of the so-called sources, which are nothing other than breweries exporting to and supplying the Latin-American countries. In order to fulfill this purpose, potential sources will be tested and, by making use of logistics tools, the scenarios that meet the demand of the region in a more effective way will be evaluated.

[pt] Descreve-se uma metodologia para planejamento da expansão da capacidade de ponta em sistemas interligados de usinas hidroelétricas. O objetivo é determinar os geradores e linhas de transmissão a serem instalados no sistema existente, de forma a suprir a carga prevista da maneira mais econômica possível, satisfazendo restrições de confiabilidade. A solução é baseada no método de decomposição de Benders, sendo o problema mestre um problema de programação inteira e o subproblema um problema estocástico de fluxo em redes. / [en] This thesis describes a methodology for peak capacity expansion of interconnected hydroelectric generating systems. The objective is to minimize investments in generators and transmission lines, subject to contraints on supply reliability. The solution approach is based on Benders decomposition, in which the master problem is an integer programming problem and the subploblem is a stochastic network flow problem.