A MINIMUM COST k-RELIABLE NETWORK INTERDICTION MODEL

摘要：

　　This paper proposes a model,named “a minimum cost k-reliable network interdiction,which minimizes the cost of setting sensors on arcs for preventing any potential threat to a protected area.Mathematically,given any directed graph with a source and a sink,several arcs need to be selected such that any path from source to sink contains at least k arcs in the selected arcs with as few resources as possible.The original model is transferred to a bilevel formulation because it is nearly impossible to be exhibited explicitly,even for the network of a moderate size.This paper also proposes an approach for resolving a bilevel program where the lower level program is a mixed integer program.A small numerical example illustrates the feasibility of our model.

关键词： Interdiction k-reliable duality LP relaxation

作者: Jia Zhao Juyun Wang Hua Yu

作者单位: University of Chinese Academy of Sciences, Beijing 100049, China Communication University of China, Beijing 100024, China

会议类型: 国际会议

会议名称: 11th International Symposium on Operations Research and its Applications(第11届运筹学及其应用国际研讨会)

会议地点: 安徽黄山

会议语种:英文

页码: 104-108

在线出版日期: 2013-08-23（万方平台首次上网日期，不代表论文的发表时间）