Robust Maximum Flow Network Interdiction Problem

In this thesis, a maximum flow-based network interdiction problem considering uncertainties in arc capacities and interdiction resource consumption is solved. The problem consists of two entities with opposing objectives: the goal of the adversary is to maximize the flow of illicit drugs through the network, while the goal of the interdictor is to minimize the maximum flow by completely interdicting arcs given a specified amount of resources. Lack of complete information about the usage patterns of the transportation network by the adversary results in an uncertain estimate of arc capacity and resources required for interdiction by the interdictor. To account for this uncertainty, a robust optimization framework is utilized, resulting in a Robust Network Interdiction Problem (RNIP). A novel mixed-integer linear program is proposed that solves the RNIP. Three heuristics are proposed to solve RNIP, the first based on Lagrangian Relaxation, the second based on Benders\u27 Decomposition, and the third based on Benders\u27 Decomposition enhanced using the Lagrangian Relaxation presolve. Computational experiments show that the third heuristic performs the best with a final MIP gap of less than 5% and a computational time saving of more than 90% for all the test networks when compared to a state-of-the-art mixed integer program solver. Sensitivity analyses are performed to identify budgets of uncertainty that provide a realistic estimate of the actual maximum flow using a Monte Carlo simulation scheme. Finally, robust decisions are compared to decisions not accounting for any uncertainty to evaluate the value of robustness. It is found that robust decisions can provide fairly accurate estimates of possible actual maximum flows in the network. When the interdiction efforts are significant, robust decisions also lead to a reduction in actual maximum flows, as much as 78% on average for a series of test networks, when compared to decisions not accounting for any uncertainty