Advancements on problems involving maximum flows

Network interdiction;Reoptimization;Robust minimum cuts;Maximum flows

Altner, Douglas S. ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Network interdiction;    Reoptimization;    Robust minimum cuts;    Maximum flows;   

Others  :  https://smartech.gatech.edu/bitstream/1853/24828/1/altner_douglas_s_200808_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

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 anintensively studied problem that has nontrivial applications in military strategy, intercepting contraband and flood control. CMFNIP is a stronglyNP-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 fewtheoretical 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 gapof 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 evenwhen 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 underlyingnetworks differ by exactly one arc. Second, we develop maximum flow reoptimization heuristics to rapidly compute a robust minimum capacity s-t cutin 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.