Journal
NETWORKS
Volume 64, Issue 2, Pages 109-124Publisher
WILEY
DOI: 10.1002/net.21561
Keywords
network interdiction; bilevel optimization; Euclidean space; space-discretization; integer programming; global optimization
Funding
- National Science Foundation [CMMI-1100765]
- Defense Threat Reduction Agency [HDTRA-10-01-0050]
- Air Force Office of Scientific Research [FA9550-12-1-0353]
- Office of Naval Research [N000141310036]
Ask authors/readers for more resources
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. (c) 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(2), 109-124 2014
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available