Survivable network design under optimal and heuristic interdiction scenarios
Tóm tắt
We examine the problem of building or fortifying a network to defend against enemy attacks in various scenarios. In particular, we examine the case in which an enemy can destroy any portion of any arc that a designer constructs on the network, subject to some interdiction budget. This problem takes the form of a three-level, two-player game, in which the designer acts first to construct a network and transmit an initial set of flows through the network. The enemy acts next to destroy a set of constructed arcs in the designer’s network, and the designer acts last to transmit a final set of flows in the network. Most studies of this nature assume that the enemy will act optimally; however, in real-world scenarios one cannot necessarily assume rationality on the part of the enemy. Hence, we prescribe optimal network design algorithms for three different profiles of enemy action: an enemy destroying arcs based on capacities, based on initial flows, or acting optimally to minimize our maximum profits obtained from transmitting flows.
Tài liệu tham khảo
Alevras D., Grötschel M., Jonas P., Paul U., Wessaly R. (1998) Survivable mobile phone network architectures: Models and solution methods. IEEE Commun. Magazine 36, 88–93
Bard J. (1983) An algorithm for solving the general bilevel programming problem. Math. Oper. Res. 8, 260–272
Bard J. (1998) Practical Bilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers, Norwell MA
Bard J., Falk J. (1982) An explicit solution to the multilevel programming problem. Comput. Oper. Res. 9, 77–100
Bialas W., Karwan M. (1984) Two-level linear programming. Manag. Sci. 30, 1004–1021
Bracken J., McGill J. (1973) Mathematical programs with optimization problems in the constraints. Oper. Res. 21, 37–44
Candler W., Townsley R. (1982) A linear two-level programming problem. Comput. Oper. Res. 9, 59–76
Clarke L., Anandalingam G. (1995) A bootstrap heuristic for designing minimum cost survivable networks. Comput. Oper. Res. 22, 921–934
Colson P.M. B., Savard G. (1998) A cutting plane algorithm for multicommodity survivable network design problems. INFORMS J. Comput. 10, 1–11
Colson P.M.B., Savard G. (2005) Bilevel programming: a survey. 4OR. 3: 87–107
Cormican K.J., Morton D.P., Wood R.K. (1998) Stochastic network interdiction. Oper. Res. 46(2): 184–196
Fortuny-Amat J., McCarl B. (1981) A representation and economic interpretation of a two-level programming problem. J. Oper. Res. Soc. 32, 783–792
Fulkerson D.R., Harding G.C. (1977) Maximizing minimum source-sink path subject to a budget constraint. Math. Program. 13(1): 116–118
Garg M., Smith J.C.: Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios. OMEGA, to appear (2006)
Israeli E., Wood R.K. (2002) Shortest-path network interdiction. Networks 40(2): 97–111
Kydland F. (1975) Hierarchical decomposition in linear economic models. Manag. Sci. 21, 1029–1039
Lim C., Smith J.C.: Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans., to appear (2006)
Magnanti L.T., Wong R.T. (1984) Network design and transportation planning: Models and algorithms. Transportation Sci. 18(1): 1–55
Minoux M. (1989) Network synthesis and optimum network design problems: Models, solution methods and applications. Networks 19(3): 313–360
Myung Y.S., Kim H.J., Tcha D.W. (1999) Design of communication networks with survivability constraints. Manag. Sci. 45, 238–252
Ouveysi I., Wirth A. (1999) On design of a survivable network architecture for dynamic routing: Optimal solution strategy and efficient heuristic. Eur. J. Oper. Res. 117, 30–44
Paul G., Tanizawa T., Havlin S., Stanley H.E. (2004) Optimization of robustness of complex networks. Eur. Phys. J. B 38, 187–191
Rajan D., Atamtürk A. (2002) Survivable network design: routing of flows and slacks. In: Anandalingam G., Raghavan S. (ed) Telecommunication Network Design and Management. Kluwer Academic Publishers Dordrecht, Boston London, pp. 65–8
Ríos M., Marianov V., Gutierrez M. (2000) Survivable capacitated network design problem: New formulation and lagrangian relaxation. J. Oper. Res. Soc. 51, 574–582
Shaio J. (2001) Constraint generation for network reliability problems. Ann. Oper. Res. 106, 155–180
Smith J.C., Sudargho F., Lim C. (2005) Survivable network design under various interdiction scenarios. San José, Spain, pp. 225–230
Vicente L., Calamai P. (1994) Bilevel and multilevel programming—a bibliography review. J. Glob. Optim. 5, 291–306
Wollmer R. (1964) Removing arcs from a network. Oper. Res. 12(6): 934–940
Wood R.K. (1993) Deterministic network interdiction. Math. Comput. Model. 17(2): 1–18