Mathematics – Optimization and Control
Scientific paper
2010-09-02
Mathematics
Optimization and Control
Submitted to INFORMS Computing Society Conference (ICS2011)
Scientific paper
Shortest path network interdiction is a combinatorial optimization problem on an activity network arising in a number of important security-related applications. It is classically formulated as a bilevel maximin problem representing an "interdictor" and an "evader". The evader tries to move from a source node to the target node along a path of the least cost while the interdictor attempts to frustrate this motion by cutting edges or nodes. The interdiction objective is to find the optimal set of edges to cut given that there is a finite interdiction budget and the interdictor must move first. We reformulate the interdiction problem for stochastic evaders by introducing a model in which the evader follows a Markovian random walk guided by the least-cost path to the target. This model can represent incomplete knowledge about the evader, and the resulting model is a nonlinear 0-1 optimization problem. We then introduce an optimization heuristic based on betweenness centrality that can rapidly find high-quality interdiction solutions by providing a global view of the network.
Gutfraind Alexander
Hagberg Aric A.
Izraelevitz David
Pan Feng
No associations
LandOfFree
Interdiction of a Markovian Evader does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Interdiction of a Markovian Evader, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interdiction of a Markovian Evader will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-684025