Exact algorithms for solving a Euclidean maximum flow network interdiction problem

Exact algorithms for solving a Euclidean maximum flow network interdiction problem

0.00 Avg rating0 Votes
Article ID: iaor201522255
Volume: 64
Issue: 2
Start Page Number: 109
End Page Number: 124
Publication Date: Sep 2014
Journal: Networks
Authors: ,
Keywords: combinatorial optimization, game theory, networks: flow, graphs, programming: integer
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.