Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks
Tóm tắt
We consider the problems of minimum-cost design and augmentation of directed network clusters that have diameter 2 and maintain the same diameter after the deletion of up to R elements (nodes or arcs) anywhere in the cluster. The property of a network to maintain not only the overall connectivity, but also the same diameter after the deletion of multiple nodes/arcs is referred to as strong attack tolerance. This paper presents the proof of NP-completeness of the decision version of the problem, derives tight theoretical bounds, as well as develops a heuristic algorithm for the considered problems, which are extremely challenging to solve to optimality even for small networks. Computational experiments suggest that the proposed heuristic algorithm does identify high-quality near-optimal solutions; moreover, in the special case of undirected networks with identical arc construction costs, the algorithm provably produces an exact optimal solution to strongly attack-tolerant two-hop network design problem, regardless of the network size.
Tài liệu tham khảo
Balasundaram B, Butenko S, Trukhanov S (2005) Novel approaches for analyzing biological networks. J Comb Optim 10:23–39
Bang-Jensen J, Chiarandini M, Morling P (2010) A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation. Networks 55(4):299–325
Bang-Jensen J, Jordán T (1998) Edge-connectivity augmentation preserving simplicity. SIAM J Discrete Math 11(4):603–623
Bendali F, Diarrassouba I, Mahjoub AR, Mailfert J (2010) The k edge-disjoint 3-hop-constrained paths polytope. Discrete Optim 7(4):222–233
Botton Q, Fortz B, Gouveia L, Poss M (2011) Benders decomposition for the hop-constrained survivable network design problem. INFORMS J Comput. doi:10.1287/ijoc.1110.0472
Conforti M, Galluccio A, Proietti G (2004) Edge-connectivity augmentation and network matrices. In: Hromkovic J, Nagl M, Westfechtel B (eds) WG. Lecture notes in computer science, vol 3353. Springer, Berlin, pp 355–364
IBM ILOG CPLEX optimization studio 12.4 (2011) http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
Dahl G, Gouveia L (2004) On the directed hop-constrained shortest path problem. Oper Res Lett 32(1):15–22
Dahl G, Huygens D, Mahjoub AR, Pesneau P (2006) On the edge-disjoint 2-hop-constrained paths polytope. Oper Res Lett 34(5):577–582
Dahl G, Johannessen B (2004) The 2-path network problem. Networks 43(3):190–199
Eswaran KP, Tarjan RE (1976) Augmentation problems. SIAM J Comput 5(4):653–665
Fico™ xpress optimization suite 7.1 (2011) http://www.fico.com/en/Products/DMTools/Pages/FICO-Xpress-Optimization-Suite.aspx
Frank A (1992) Augmenting graphs to meet edge-connectivity requirements. SIAM J Discrete Math 5(1):25–53
Frank A (1994) Connectivity augmentation problems in network design. In: Birge J, Murty KG (eds) Mathematical programming: state of the art. University of Michigan Press, Ann Arbor, pp 34–63
Fured Z, Horak P, Pareek CM, Zhu X (1998) Minimal oriented graphs of diameter 2. Graphs Comb 14:345–350
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York
Gouveia L, Patricio P, Sousa A (2008) Hop-constrained node survivable network design: an application to mpls over wdm. Netw Spat Econ 8(1):3–21
Hsu TS (2002) Simpler and faster biconnectivity augmentation. J Algorithms 45(1):55–71
Huygens D, Labbé M, Mahjoub AR, Pesneau P (2007) The two-edge connected hop-constrained network design problem: valid inequalities and branch-and-cut. Networks 49(1):116–133
Huygens D, Mahjoub AR, Pesneau P (2004) Two edge-disjoint hop-constrained paths and polyhedra. SIAM J Discrete Math 18(2):287–312
Ishii T, Nagamochi H (2000) On the minimum augmentation of an l-connected graph to a k-connected graph. In: SWAT, pp 286–299
Li CL, McCormick S, Simchi-Levi D (1992) On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems. Oper Res Lett 11:303–308
Ljubić I (2010) A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation. Networks 56(3):169–182
Meijer H, Dawes R (1988) Fault tolerant networks of specified diameter. In: van Leeuwen J (ed) WG. Lecture notes in computer science, vol 344. Springer, Berlin, pp 74–86
Mokken RJ (1979) Cliques, clubs and clans. Qual Quant 13(2):161–173
Murty USR (1968) On critical graphs of diameter 2. Math Mag, 138–140
Pirkul H, Soni S (2003) New formulations and solution procedures for the hop constrained network design problem. Eur J Oper Res 148(1):126–140
Schumacher U (1984) An algorithm for construction of a k-connected graph with minimum number of edges and quasiminimal diameter. Networks 14:63–74
Soneoka T, Nakada H, Imase M (1990) Design of a d-connected digraph with a minimum number of edges and a quasiminimal diameter. Discrete Appl Math 27:255–265
Veremyev A, Boginski V (2012a) Identifying large robust network clusters via new compact formulations of maximum k-club problems. Eur J Oper Res 218:316–326
Veremyev A, Boginski V (2012b) Robustness and strong attack tolerance of low-diameter networks. In: Sorokin A, Murphey R, Thai MT, Pardalos PM (eds) Dynamics of information systems: mathematical foundations. Springer, Berlin (to appear)