2015, Volume 17, Issue 1
Strategic Study of CAE >> 2015, Volume 17, Issue 1
A maximum reliable network interdiction model with limited resources
College of Engineering and Information Technology, University of Chinese Academy of Sciences, Beijing 100049, China
Next Previous
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
References
[ 1 ] Wollmer R. Removing arcs from a network[J]. Operations Research, 1964, 12(6): 934-940. link1
[ 2 ] Durbin E. An interdiction model of highway transportation[R]. RM-4945-PR, RAND Research Memorandum, 1966. link1
[ 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. link1
[ 4 ] Steinrauf R L. Network interdiction models[R]. Naval Postgraduate School Monterey CA, 1991. link1
[ 5 ] Wood R K. Deterministic network interdiction[J]. Mathematical and Computer Modelling, 1993, 17(2): 1-18. link1
[ 6 ] Benders J F. Partitioning procedures for solving mixed-variables programming problems[J]. Numerische mathematik, 1962, 4(1): 238-252. link1
[ 7 ] Wagner D K. Disjoint (s, t) cuts in a network[J]. Networks, 1990, 20(4): 361-371. link1
[ 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. link1
[ 9 ] Lim C, Smith J C. Algorithms for discrete and continuous multicommodity flow network interdiction problems[J]. IIE Transactions, 2007, 39(1): 15-26. link1
[10] Cormican K J, Morton D P, Wood R K. Stochastic network interdiction[J]. Operations Research, 1998, 46(2): 184-197. link1
[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. link1
[12] KettlDF.contingentcoordinationpracticalandtheoreticalpuzzlesfor homeland security[J]. The American Review of Public Administration, 2003, 33(3): 253-277. link1
[13] Brown G, Carlyle M, Salmerón J, et al. Defending critical infrastructure[J]. Interfaces, 2006, 36(6): 530-544. link1
[14] Morton D P, Pan F, Saeger K J. Models for nuclear smuggling interdiction[J]. IIE Transactions, 2007, 39(1): 3-14. link1
[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. link1
[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. link1
京公网安备 11010502051620号
