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.

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

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.

De part et d’autre de la Terre, on observe de plus en plus de phénomènes naturels dévastateurs, parmi lesquels les inondations constituent l’une des catastrophes les plus fréquentes. Ces dernières décennies d’importantes inondations ont été induites par les crues de rivières. Ces crues, dues à des pluies excessives ou aux eaux de ruissellement, causent sans cesse des pertes de vies humaines et des dégâts matériels importants. Pour remédier à ces problèmes, les réseaux hydrographiques sont de plus en plus équipés de moyens de détection de crues. Un facteur essentiel à la gestion de tels phénomènes est la réactivité. En effet, les gestionnaires des réseaux hydrographiques, dans ce genre de situation, doivent prendre rapidement des décisions importantes dans un contexte incertain, car la plupart de ces crues sont le fruit de phénomènes climatiques brusques, dont l’ampleur est difficile à évaluer avec précision. Nous proposons, dans ce mémoire, une méthode de gestion des crues dans des réseaux hydrographiques équipés de zones inondables contrôlées par des portes gravitationnelles. Dans un premier temps, nous avons modélisé notre méthode de gestion à l’aide d’un réseau de transport statique. Dans un second temps, nous l’avons enrichi en utilisant les réseaux de transport à retards dans le but de prendre en compte les temps de déplacement de la ressource gérée. Afin de pallier le problème de la taille importante des réseaux de transport à retards, nous avons élaboré un mécanisme de substitution combinant un réseau de transport statique réduit et une matrice de temporisation. De plus, ce mécanisme autorise la prise en compte des temps de transfert variables dépendant des débits, sans modification ni du réseau de transport, ni de la structure de la matrice de temporisation. Ce mécanisme permet donc une gestion simplifiée des temps de transferts, variables ou non. Avec ce mécanisme, l’évaluation du flot maximal à coût minimum, nous a permis, suivant les stratégies de gestion considérées, de consigner l’ouverture des portes des zones inondables afin d’écrêter la crue mais aussi afin de restituer cette eau stockée au moment opportun. Finalement, afin d’évaluer les apports de cette gestion, la méthode a été appliquée sur un cas d’étude basée sur un tronçon de rivière équipé de trois zones inondables et modélisé à l’aide de simulateurs hydrauliques combinant les approches de modélisation 1D et 2D. Les résultats de simulation obtenus ont montré que l’approche proposée permettait de réduire de manière significative les inondations en aval des cours d’eau. / On either side of the Earth, we observe more and more devastating natural phenomena. Amon these phenomena, floods are one of the most frequent and devastating natural disasters. During these last decades extensive flooding were caused by the flood of rivers. These floods due to excessive rainfall or runoff induce invariably the loss of human lives and material damages. To overcome these problems, water systems are increasingly equipped with means for detecting floods. A key factor in the management of such phenomena is responsiveness. Indeed, managers of river systems, faced to this kind of situation should quickly take important decisions in an uncertain context, as most of these floods are induced by abrupt climate events, whose magnitude is difficult to assess accuracy. We propose in this dissertation, a method of flood management in river systems equipped with flood zones controlled by gravitational gates. At first, we modeled our management method using a static transportation network. In a second step, we enriched it by using transportation networks with delays in order to take into account the travel time of the managed resource. The main difficulty of transportation networks with delays is their oversize. To overcome this problem, we developed an alternative mechanism combining a static reduced transportation network with a temporization matrix. Furthermore, this mechanism allows the consideration of variable time transfer depending on flows, without modification either on the transportation network, or on the structure of the temporization matrix. This mechanism allows simplified management of the transfer times, variable or not. With this mechanism, the evaluation of the minimum cost maximum flow allowed us, according to the management strategies considered, to compute the gate opening for floodplains in order to mitigate the flood but also to restore the water stored at the relevant time. Finally, to evaluate the contributions of this management, the method was applied to a case study based on a section of river equipped with three flood control reservoirs areas modeled using hydraulic simulators combining 1D and 2D models. The simulation results showed that the proposed approach allowed reducing significantly the floods downstream watercourses.

abstract: Short-notice disasters such as hurricanes involve uncertainties in many facets, from the time of its occurrence to its impacts’ magnitude. Failure to incorporate these uncertainties can affect the effectiveness of the emergency responses. In the case of a hurricane event, uncertainties and corresponding impacts during a storm event can quickly cascade. Over the past decades, various storm forecast models have been developed to predict the storm uncertainties; however, access to the usage of these models is limited. Hence, as the first part of this research, a data-driven simulation model is developed with aim to generate spatial-temporal storm predicted hazards for each possible hurricane track modeled. The simulation model identifies a means to represent uncertainty in storm’s movement and its associated potential hazards in the form of probabilistic scenarios tree where each branch is associated with scenario-level storm track and weather profile. Storm hazards, such as strong winds, torrential rain, and storm surges, can inflict significant damage on the road network and affect the population’s ability to move during the storm event. A cascading network failure algorithm is introduced in the second part of the research. The algorithm takes the scenario-level storm hazards to predict uncertainties in mobility states over the storm event. In the third part of the research, a methodology is proposed to generate a sequence of actions that simultaneously solve the evacuation flow scheduling and suggested routes which minimize the total flow time, or the makespan, for the evacuation process from origins to destinations in the resulting stochastic time-dependent network. The methodology is implemented for the 2017 Hurricane Irma case study to recommend an evacuation policy for Manatee County, FL. The results are compared with evacuation plans for assumed scenarios; the research suggests that evacuation recommendations that are based on single scenarios reduce the effectiveness of the evacuation procedure. The overall contributions of the research presented here are new methodologies to: (1) predict and visualize the spatial-temporal impacts of an oncoming storm event, (2) predict uncertainties in the impacts to transportation infrastructure and mobility, and (3) determine the quickest evacuation schedule and routes under the uncertainties within the resulting stochastic transportation networks. / Dissertation/Thesis / Doctoral Dissertation Industrial Engineering 2020