A maximum reliable network interdiction model with limited resources

Zhao Jia、Yu Hua

Strategic Study of CAE ›› 2015, Vol. 17 ›› Issue (1) : 137-142.

PDF(1103 KB)
PDF(1103 KB)
Strategic Study of CAE ›› 2015, Vol. 17 ›› Issue (1) : 137-142.

A maximum reliable network interdiction model with limited resources

  • Zhao Jia、Yu Hua

Author information +
History +

Abstract

This paper proposes a maximum reliable network interdiction model, which is to maximize the reliability of an interdicting network with limited resources by setting sensors in arcs to prevent any flow between given two nodes in a given graph even though some sensors could be failed, i.e., given a directed graph with a source and a sink, several arcs need to be selected such that each path from the source to the sink contains as many arcs in the selected subset as possible. In any given graph, the number of paths between any given two nodes is exponential to the size of this graph, so this model is transferred to a bilevel program. We solve this bilevel integer program by finding out the relationship between the lower level integer program and its linear program relaxation, also using the duality theory because a bilevel program is intractable in common sense. Lastly, we reduce the number of the constraint to one order of the size of the graph from its exponential order. Besides, we also demonstrate an approach to resolve the bilevel program.

Keywords

interdiction model / k-reliability / duality / linear programming relaxation / complementary slackness

Cite this article

Download citation ▾
Zhao Jia and Yu Hua. A maximum reliable network interdiction model with limited resources. Strategic Study of CAE, 2015, 17(1): 137‒142
AI Summary AI Mindmap
PDF(1103 KB)

Accesses

Citations

Detail

Sections
Recommended

/