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

2015年第17卷第1期

摘要

关键词

参考文献

相关研究

回顶部

《中国工程科学》 >> 2015年第17卷第1期

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

中国科学院大学工程管理与信息技术学院，北京 100049

资助项目：国家重点基础研究发展计划(973计划)(2011CB706900) 收稿日期： 2014-02-24 发布日期： 2015-01-13 10:39:05.000

HTML67 PDF 16 收藏 0

摘要

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

关键词

中断模型 ; k-可靠性 ; 对偶 ; 线性规划松弛 ; 互补松弛型

参考文献

[ 1 ] Wollmer R. Removing arcs from a network[J]. Operations Research, 1964, 12(6): 934-940. 链接1

[ 2 ] Durbin E. An interdiction model of highway transportation[R]. RM-4945-PR, RAND Research Memorandum, 1966. 链接1

[ 3 ] Simaan M, Cruz Jr J B. On the Stackelberg strategy in nonzerosum games[J]. Journal of Optimization Theory and Applications, 1973, 11(5): 533-555. 链接1

[ 4 ] Steinrauf R L. Network interdiction models[R]. Naval Postgraduate School Monterey CA, 1991. 链接1

[ 5 ] Wood R K. Deterministic network interdiction[J]. Mathematical and Computer Modelling, 1993, 17(2): 1-18. 链接1

[ 6 ] Benders J F. Partitioning procedures for solving mixed-variables programming problems[J]. Numerische mathematik, 1962, 4(1): 238-252. 链接1

[ 7 ] Wagner D K. Disjoint (s, t) cuts in a network[J]. Networks, 1990, 20(4): 361-371. 链接1

[ 8 ] Barnhart C, Johnson E L, Nemhauser G L, et al. Branch- andprice: Column generation for solving huge integer programs[J]. Operations Research, 1998, 46(3): 316-329. 链接1

[ 9 ] Lim C, Smith J C. Algorithms for discrete and continuous multicommodity flow network interdiction problems[J]. IIE Transactions, 2007, 39(1): 15-26. 链接1

[10] Cormican K J, Morton D P, Wood R K. Stochastic network interdiction[J]. Operations Research, 1998, 46(2): 184-197. 链接1

[11] Berry J W, Fleischer L, Hart W E, et al. Sensor placement in municipal water networks[J]. Journal of Water Resources Planning and Management, 2005, 131(3): 237-243. 链接1

[12] KettlDF.contingentcoordinationpracticalandtheoreticalpuzzlesfor homeland security[J]. The American Review of Public Administration, 2003, 33(3): 253-277. 链接1

[13] Brown G, Carlyle M, Salmerón J, et al. Defending critical infrastructure[J]. Interfaces, 2006, 36(6): 530-544. 链接1

[14] Morton D P, Pan F, Saeger K J. Models for nuclear smuggling interdiction[J]. IIE Transactions, 2007, 39(1): 3-14. 链接1

[15] Scaparra M P, Church R L. A bilevel mixed-integer program for critical infrastructure protection planning[J]. Computers & Operations Research, 2008, 35(6): 1905-1923. 链接1

[16] Royset J O, Wood R K. Solving the bi-objective maximum-flow network- interdiction problem[J]. Ineorms Journal on Computing, 2007, 19(2): 175-184. 链接1