Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks

详细信息    查看全文

• 作者：Grigory Pastukhov (1)
  Alexander Veremyev (1)
  Vladimir Boginski (1)
  Eduardo L. Pasiliao (1) (2)
  
• 关键词：Network design ; Strong attack tolerance ; R ; Robust 2 ; clubs ; Combinatorial optimization ; Heuristics
• 刊名：Journal of Combinatorial Optimization
• 出版年：2014
• 出版时间：April 2014
• 年：2014
• 卷：27
• 期：3
• 页码：462-486
• 全文大小：929 KB
• 参考文献：1. Balasundaram B, Butenko S, Trukhanov S (2005) Novel approaches for analyzing biological networks. J聽Comb Optim 10:23鈥?9 CrossRef
  2. Bang-Jensen J, Chiarandini M, Morling P (2010) A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation. Networks 55(4):299鈥?25
  3. Bang-Jensen J, Jord谩n T (1998) Edge-connectivity augmentation preserving simplicity. SIAM J Discrete Math 11(4):603鈥?23 CrossRef
  4. Bendali F, Diarrassouba I, Mahjoub AR, Mailfert J (2010) The / k edge-disjoint 3-hop-constrained paths polytope. Discrete Optim 7(4):222鈥?33 CrossRef
  5. 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
  6. 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鈥?64
  7. IBM ILOG CPLEX optimization studio 12.4 (2011) http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
  8. Dahl G, Gouveia L (2004) On the directed hop-constrained shortest path problem. Oper Res Lett 32(1):15鈥?2 CrossRef
  9. Dahl G, Huygens D, Mahjoub AR, Pesneau P (2006) On the edge-disjoint 2-hop-constrained paths polytope. Oper Res Lett 34(5):577鈥?82 CrossRef
  10. Dahl G, Johannessen B (2004) The 2-path network problem. Networks 43(3):190鈥?99 CrossRef
  11. Eswaran KP, Tarjan RE (1976) Augmentation problems. SIAM J Comput 5(4):653鈥?65 CrossRef
  12. Fico<sup>鈩?/sup> xpress optimization suite 7.1 (2011) http://www.fico.com/en/Products/DMTools/Pages/FICO-Xpress-Optimization-Suite.aspx
  13. Frank A (1992) Augmenting graphs to meet edge-connectivity requirements. SIAM J Discrete Math 5(1):25鈥?3 CrossRef
  14. 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鈥?3
  15. Fured Z, Horak P, Pareek CM, Zhu X (1998) Minimal oriented graphs of diameter 2. Graphs Comb 14:345鈥?50 CrossRef
  16. Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York
  17. 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鈥?1 CrossRef
  18. Hsu TS (2002) Simpler and faster biconnectivity augmentation. J Algorithms 45(1):55鈥?1 CrossRef
  19. 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鈥?33 CrossRef
  20. Huygens D, Mahjoub AR, Pesneau P (2004) Two edge-disjoint hop-constrained paths and polyhedra. SIAM J Discrete Math 18(2):287鈥?12 CrossRef
  21. Ishii T, Nagamochi H (2000) On the minimum augmentation of an / l-connected graph to a / k-connected graph. In: SWAT, pp 286鈥?99
  22. 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鈥?08 CrossRef
  23. Ljubi膰 I (2010) A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation. Networks 56(3):169鈥?82 CrossRef
  24. 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鈥?6
  25. Mokken RJ (1979) Cliques, clubs and clans. Qual Quant 13(2):161鈥?73 CrossRef
  26. Murty USR (1968) On critical graphs of diameter 2. Math Mag, 138鈥?40
  27. Pirkul H, Soni S (2003) New formulations and solution procedures for the hop constrained network design problem. Eur J Oper Res 148(1):126鈥?40 CrossRef
  28. Schumacher U (1984) An algorithm for construction of a / k-connected graph with minimum number of edges and quasiminimal diameter. Networks 14:63鈥?4 CrossRef
  29. 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鈥?65 CrossRef
  30. 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鈥?26 CrossRef
  31. 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)</sup>
  
• 作者单位：Grigory Pastukhov (1)
  Alexander Veremyev (1)
  Vladimir Boginski (1)
  Eduardo L. Pasiliao (1) (2)
  
  1. Industrial and Systems Engineering Department, University of Florida, 303 Weil Hall, Gainesville, FL, 32611, USA
  2. Air Force Research Laboratory, Munitions Directorate, Eglin AFB, FL, 32542, USA
  
• ISSN：1573-2886

文摘

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.