有限资源下最大可靠性网络流中断模型

A maximum reliable network interdiction model with limited resources

提出了最大可靠性网络流中断模型。此模型是在给定的网络图中,通过在边上设置监测点来阻止给定两个顶点之间的网络流量,同时考虑所设置监测点失效的可能,在给定的资源限制下,最大化中断网络流的可能性,即给定起点和终点的网络图,在资源有限的情况下,选择一些边设置监测点使得从起点到终点的所有路都包含尽可能多的已被设置中断点的边。在给定图中,两点之间的路的条数是图的规模的指数次幂,为此将此模型转化为双层整数规划模型,鉴于双层整数规划模型在一般情况下是不可解的,通过探讨下层整数规划问题与其线性规划松弛之间的关系以及线性规划对偶理论来解此双层整数规划模型。本文不仅将该模型约束的个数从图的规模的指数次幂降到一次幂,同时也提供了一种解双层整数规划问题的方法。

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 se-lected such that each path from the source to the sink contains as many arcs in the selected sub-set as possible. In any given graph,the number of paths between any given two nodes is expo-nential 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 in-tractable 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 re-solve the bilevel program.