Exact Algorithms for Solving a Euclidean Maximum Flow Network Interdiction Problem

摘要

We consider an interdiction problem that involves an operator (or defender) whose goal is to maximize flow from a source node to a sink node in some network that resides in Euclidean space. The problem we examine takes the perspective of an interdictor, who seeks to minimize the defender's maximum flow by locating a set of attacks that diminish arc capacities in accordance with the distance from the arc to the attack. Attacks are not restricted to node or arc locations, and can occur anywhere on the region in which the network is located. We refer to this problem as the Euclidean maximum flow network interdiction problem (E-MFNIP). We show that E-MFNIP is NP-hard, as it generalizes the maximum flow interdiction problem studied by Wood. This article contributes two approaches to solving E-MFNIP based on solving a sequence of lower-bounding integer programs from which upper bounds can be readily obtained, and shows that these bounds are convergent. Computations on a set of test instances indicate that an approach based on space-discretization tends to converge much faster than one based on linearizing the nonlinear capacity functions. We demonstrate the application of our space-discretization approach on a real geographical network.