This thesis presents new results on a few problems involving maximum flows. The first topic we explore is maximum flow network interdiction. The second topic we explore is reoptimization heuristics for rapidly solving an entire sequence of Maximum Flow Problems. In the Cardinality Maximum Flow Network Interdiction Problem (CMFNIP), an interdictor chooses R arcs to delete from an s-t flow network so as to minimize the maximum flow on the network induced on the undeleted arcs. This is an intensively studied problem that has nontrivial applications in military strategy, intercepting contraband and flood control. CMFNIP is a strongly NP-hard special case of the Maximum Flow Network Interdiction Problem (MFNIP), where each arc has an interdiction cost and the interdictor is constrained by an interdiction budget. Although there are several papers on MFNIP, very few theoretical results have been documented. In this talk, we introduce two exponentially large classes of valid inequalities for CMFNIP and prove that they can be separated in polynomial time. Second, we prove that the integrality gap of the commonly used integer linear programming formulation for CMFNIP is contained in the set Omega(|V| ^(1 e)) where |V| is the number of nodes in the network and e is in the interval (0,1). We prove that this result holds even when the linear programming relaxation is strengthened with our two classes of valid inequalities and we note that this result immediately extends to MFNIP. In the second part of this defense, we explore incremental algorithms for solving an online sequence of Maximum Flow Problems (MFPs). Sequences of MFPs arise in a diverse collection of settings including computational biology, finger biometry, constraint programming and real-time scheduling. To initiate this study, we develop an algorithm for solving a sequence of MFPs when the ith MFP differs from the (i-1)st MFP, for each possible i, in that the underlying networks differ by exactly one arc. Second, we develop maximum flow reoptimization heuristics to rapidly compute a robust minimum capacity s-t cut in light of uncertain arc capacities. Third, we develop heuristics to efficiently compute a maximum expected maximum flow in the context of two-stage stochastic programming. We present computational results illustrating the practical performance of our algorithms.

Estudos hidrológicos são extremamente importantes em projetos de obras lineares, nas quais o traçado deve minimizar o risco de instabilidade tanto na fase de construção como na fase de operação. O escoamento superficial, além de ser um parâmetro fundamental para a definição do traçado e dos projetos subsequentes, influencia diretamente a dinâmica dos processos geológico-geotécnicos na área do empreendimento. A presente pesquisa propõe um método para realizar uma estimativa das vazões máximas nas travessias de obras civis lineares, integrando modelos hidrológicos obtidos com Sistema de Informação Geográfica (SIG) e métodos usuais de cálculo de vazões de cheia. O método foi aplicado em um setor do oleoduto São Paulo – Brasília (OSBRA), entre os municípios de São Simão e Cravinhos (SP). O modelo hidrológico foi obtido no software ArcGIS 9.3, a partir da definição de uma área mínima de contribuição de 5 hectares, adequada para a escala da base cartográfica digital (1:10.000) e para as características da área de estudo. As 29 bacias de contribuição delimitadas foram posteriormente validadas na vistoria de campo. A compatibilidade entre as bacias geradas pelo modelo hidrológico e as bacias identificadas visualmente na área de estudo foi satisfatória. As vazões máximas foram calculadas pelo Método Racional (bacias com área inferior a 2 km²) e pelo Método Racional Modificado (bacias com área superior a 2 km²), que abrangeu o Método de McMath, o Método Racional com expoente redutor de área e o Método Racional com coeficiente de retardo, sendo o último o que apresentou os resultados mais razoáveis. O cálculo das vazões de cheia foi realizado para períodos de retorno de 10 e 50 anos, a partir dos quais foram gerados Mapas de Vazões Máximas, que foram utilizados para inferência de riscos de eventos perigosos de natureza geológico-geotécnica causados pela ação das águas pluviais na região do oleoduto. Como o traçado do oleoduto foi posicionado ao longo dos divisores principais, não foram identificados locais críticos. Posteriormente, o traçado do oleoduto foi utilizado como referência para uma aplicação do método proposto em um projeto de drenagem. As bacias com valores de vazões máximas classificados com muito baixos não foram incluídas devido aos fluxos pouco significativos. Para as bacias com valores de vazões de cheia classificados como baixos e médios, sugeriu-se a utilização de dispositivos de drenagem superficial. Para as bacias com vazões máximas classificadas como altas e muito altas, foi proposta a utilização de dispositivos de drenagem de transposição de talvegues. Os resultados obtidos na pesquisa permitiram a consolidação do método proposto para aplicação em outros tipos de obras lineares e em locais com diferentes características ambientais. / Hydrological studies are extremely important in linear constructions projects, in which the routing must minimize the risk of instability both during construction and in operation phase. The surface runoff, in addition of being a fundamental parameter to routing definition and subsequent projects, directly influences the dynamics of geological-geotechnical processes in the enterprise area. The present research proposes a method to estimate maximum flows in crossing locations in linear civil constructions, integrating hydrological models obtained with Geographic Information System (GIS) and usual methods of peak flows calculation. The method was applied in a sector of São Paulo – Brasília (OSBRA) oil pipeline, between the municipalities of São Simão and Cravinhos (SP). The hydrological model was obtained in ArcGIS 9.3 software, from the definition of a minimal area of contribution of 5 hectares, adequate for the scale of the digital cartographic base (1:10.000) and for the study area characteristics. The 29 delimited watersheds were subsequently validated in the field visit. The compatibility between watersheds generated in the hydrological model and watersheds visually identified in the study area was satisfactory. The maximum flows were calculated by Rational Method (watersheds with area less than 2 km²) e by Modified Rational Method (watersheds with area higher than 2 km²), which included McMath Method, Rational Method with reducing exponent area and Rational Method with retard coefficient, and the latter presented the most reasonable results. Peak flows calculation was performed for return periods of 10 and 50 years, from which were generated Maximum Flows Maps, which were used for inference of risks of hazardous events of geological-geotechnical nature caused by rainwater action in the pipeline region. The pipeline routing was positioned along the main dividers, therefore critical locations were not identified. Subsequently, the pipeline routing was used as a reference for application of the proposed method in a drainage project. Basins with maximum flows classified as very low were not included due to its low significance flows. For basins with peak flows values classified as low and medium, it was suggested the use of surface drainage devices. For basin with maximum flows classified as high and very high, it was proposed the use of thalwegs transposition drainage devices. The results obtained in the research allowed the consolidation of the proposed method to application in other types of linear constructions and in locals with different environmental characteristics.

Estudos hidrológicos são extremamente importantes em projetos de obras lineares, nas quais o traçado deve minimizar o risco de instabilidade tanto na fase de construção como na fase de operação. O escoamento superficial, além de ser um parâmetro fundamental para a definição do traçado e dos projetos subsequentes, influencia diretamente a dinâmica dos processos geológico-geotécnicos na área do empreendimento. A presente pesquisa propõe um método para realizar uma estimativa das vazões máximas nas travessias de obras civis lineares, integrando modelos hidrológicos obtidos com Sistema de Informação Geográfica (SIG) e métodos usuais de cálculo de vazões de cheia. O método foi aplicado em um setor do oleoduto São Paulo – Brasília (OSBRA), entre os municípios de São Simão e Cravinhos (SP). O modelo hidrológico foi obtido no software ArcGIS 9.3, a partir da definição de uma área mínima de contribuição de 5 hectares, adequada para a escala da base cartográfica digital (1:10.000) e para as características da área de estudo. As 29 bacias de contribuição delimitadas foram posteriormente validadas na vistoria de campo. A compatibilidade entre as bacias geradas pelo modelo hidrológico e as bacias identificadas visualmente na área de estudo foi satisfatória. As vazões máximas foram calculadas pelo Método Racional (bacias com área inferior a 2 km²) e pelo Método Racional Modificado (bacias com área superior a 2 km²), que abrangeu o Método de McMath, o Método Racional com expoente redutor de área e o Método Racional com coeficiente de retardo, sendo o último o que apresentou os resultados mais razoáveis. O cálculo das vazões de cheia foi realizado para períodos de retorno de 10 e 50 anos, a partir dos quais foram gerados Mapas de Vazões Máximas, que foram utilizados para inferência de riscos de eventos perigosos de natureza geológico-geotécnica causados pela ação das águas pluviais na região do oleoduto. Como o traçado do oleoduto foi posicionado ao longo dos divisores principais, não foram identificados locais críticos. Posteriormente, o traçado do oleoduto foi utilizado como referência para uma aplicação do método proposto em um projeto de drenagem. As bacias com valores de vazões máximas classificados com muito baixos não foram incluídas devido aos fluxos pouco significativos. Para as bacias com valores de vazões de cheia classificados como baixos e médios, sugeriu-se a utilização de dispositivos de drenagem superficial. Para as bacias com vazões máximas classificadas como altas e muito altas, foi proposta a utilização de dispositivos de drenagem de transposição de talvegues. Os resultados obtidos na pesquisa permitiram a consolidação do método proposto para aplicação em outros tipos de obras lineares e em locais com diferentes características ambientais. / Hydrological studies are extremely important in linear constructions projects, in which the routing must minimize the risk of instability both during construction and in operation phase. The surface runoff, in addition of being a fundamental parameter to routing definition and subsequent projects, directly influences the dynamics of geological-geotechnical processes in the enterprise area. The present research proposes a method to estimate maximum flows in crossing locations in linear civil constructions, integrating hydrological models obtained with Geographic Information System (GIS) and usual methods of peak flows calculation. The method was applied in a sector of São Paulo – Brasília (OSBRA) oil pipeline, between the municipalities of São Simão and Cravinhos (SP). The hydrological model was obtained in ArcGIS 9.3 software, from the definition of a minimal area of contribution of 5 hectares, adequate for the scale of the digital cartographic base (1:10.000) and for the study area characteristics. The 29 delimited watersheds were subsequently validated in the field visit. The compatibility between watersheds generated in the hydrological model and watersheds visually identified in the study area was satisfactory. The maximum flows were calculated by Rational Method (watersheds with area less than 2 km²) e by Modified Rational Method (watersheds with area higher than 2 km²), which included McMath Method, Rational Method with reducing exponent area and Rational Method with retard coefficient, and the latter presented the most reasonable results. Peak flows calculation was performed for return periods of 10 and 50 years, from which were generated Maximum Flows Maps, which were used for inference of risks of hazardous events of geological-geotechnical nature caused by rainwater action in the pipeline region. The pipeline routing was positioned along the main dividers, therefore critical locations were not identified. Subsequently, the pipeline routing was used as a reference for application of the proposed method in a drainage project. Basins with maximum flows classified as very low were not included due to its low significance flows. For basins with peak flows values classified as low and medium, it was suggested the use of surface drainage devices. For basin with maximum flows classified as high and very high, it was proposed the use of thalwegs transposition drainage devices. The results obtained in the research allowed the consolidation of the proposed method to application in other types of linear constructions and in locals with different environmental characteristics.

Finding bottlenecks and eliminating them to increase the overall flow of a network often appears in real world applications, such as production planning, factory layout, flow related physical approaches, and even cyber security. In many cases, several edges can form a bottleneck (cascaded bottlenecks). This work presents a visual analytics methodology to analyze these cascaded bottlenecks. The methodology consists of multiple steps: identification of bottlenecks, identification of potential improvements, communication of bottlenecks, interactive adaption of bottlenecks, and a feedback loop that allows users to adapt flow networks and their resulting bottlenecks until they are satisfied with the flow network configuration. To achieve this, the definition of a minimal cut is extended to identify network edges that form a (cascaded) bottleneck. To show the effectiveness of the presented approach, we applied the methodology to two flow network setups and show how the overall flow of these networks can be improved.