Robust Critical Node Selection by Benders Decomposition

References

• Addis B, Summa MD, Grosso A (2013) Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth. Discrete Appl. Math. 161(16–17):2349–2360.Crossref, Google Scholar
• Arulselvan A, Commander CW, Pardalos PM, Shylo O (2007) Managing network risk via critical node identification. Gülpınar N, Rustem B, eds. Risk Management in Telecommunication Networks (Springer, Berlin), 474–477.Google Scholar
• Arulselvan A, Commander CW, Shylo O, Pardalos PM (2011) Cardinality-constrained critical node detection problem. Gülpınar N, Harrison P, Rustem B, eds. Performance Models and Risk Management CommunicationSystems, Springer Optimization and Its Applications, Vol. 46 (Springer, New York), 79–91.Crossref, Google Scholar
• Ben-Tal A, Ghaoui LE, Nemirovski A (2009) Robust Optimization, Princeton Series in Applied Mathematics (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Bertsimas D, Sim M (2004a) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Sim M (2004b) Robust discrete optimization under ellipsoidal uncertainty sets. Technical report, Massachusetts Institute of Technology, Cambridge, MA. http://web.mit.edu/dbertsim/www/papers.html.Google Scholar
• Cohen R, Havlin S, Ben-Avraham D (2003) Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett. 91(24):247901–247905.Crossref, Google Scholar
• Commander CW, Pardalos PM, Ryabchenko V, Uryasev S, Zrazhevsky G (2007) The wireless network jamming problem. J. Combinatorial Optim. 14(4):481–498.Crossref, Google Scholar
• Di Summa M, Grosso A, Locatelli M (2011) Complexity of the critical node problem over trees. Comput. Oper. Res. 38(12):1766–1774.Crossref, Google Scholar
• Di Summa M, Grosso A, Locatelli M (2012) Branch and cut algorithms for detecting critical nodes in undirected graphs. Comput. Optim. Appl. 53(3):649–680.Crossref, Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Fan N, Pardalos PM (2010a) Linear and quadratic programming approaches for the general graph partitioning problem. J. Global Optim. 48(1):57–71.Crossref, Google Scholar
• Fan N, Pardalos PM (2010b) Robust optimization of graph partitioning and critical node detection in analyzing networks. Wu W, Daescu O, eds. Combinatorial Optim. Appl., Lecture Notes in Computer Science, Vol. 6508 (Springer, Berlin), 170–183.Crossref, Google Scholar
• Fan N, Zheng QP, Pardalos PM (2012) Robust optimization of graph partitioning involving interval uncertainty. Theoret. Comput. Sci. 447:53–61.Crossref, Google Scholar
• Floyd R (1962) Algorithm 97: Shortest path. Comm. ACM 5(6):345.Crossref, Google Scholar
• Garg N, Vazirani VV, Yannakakis M (1996) Approximate max-flow min-(multi) cut theorems and their applications. SIAM J. Comput. 25(2):235–251.Crossref, Google Scholar
• Geoffrion AM (1972) Generalized Benders decomposition. J. Optim. Theory Appl. 10(4):237–260.Crossref, Google Scholar
• Ghaddar B, Anjos M, Liers F (2011) A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem. Ann. Oper. Res. 188(1):155–174.Crossref, Google Scholar
• Hopcroft J, Tarjan R (1973) Efficient algorithms for graph manipulation. Comm. ACM 16(6):372–378.Crossref, Google Scholar
• Li M, Gabriel SA, Shim Y, Azarm S (2011) Interval uncertainty-based robust optimization for convex and non-convex quadratic programs with applications in network infrastructure planning. Networks Spatial Econom. 11(1):159–191.Crossref, Google Scholar
• Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Montemanni R (2006) A Benders decomposition approach for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 174(3):1479–1490.Crossref, Google Scholar
• Naoum-Sawaya J, Elhedhli S (2013) An interior-point Benders based branch-and-cut algorithm for mixed integer programs. Ann. Oper. Res. 210(1):33–55.Crossref, Google Scholar
• Saito H, Murota K (2007) Benders decomposition approach to robust mixed integer programming. Pacific J. Optim. 3(1):99–112.Google Scholar
• Shen S, Smith JC (2012) Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs. Networks 60(2):103–119.Crossref, Google Scholar
• Shen S, Smith JC, Goli R (2012) Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optim. 9(3):172–188.Crossref, Google Scholar
• Siddiqui S, Azarm S, Gabriel S (2011) A modified Benders decomposition method for efficient robust optimization under interval uncertainty. Structural Multidisciplinary Optim. 44(2):259–275.Crossref, Google Scholar
• Siddiqui S, Gabriel SA, Azarm S (2014) Solving mixed-integer robust optimization problems with interval uncertainty using Benders decomposition. J. Oper. Res. Soc. 66(4):664–673.Crossref, Google Scholar
• Tao Z, Zhongqian F, Binghong W (2006) Epidemic dynamics on complex networks. Progress Natural Sci. 16(5):452–457.Crossref, Google Scholar
• Ventresca M (2012) Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem. Comput. Oper. Res. 39(11):2763–2775.Crossref, Google Scholar
• Ventresca M, Aleman D (2014) A derandomized approximation algorithm for the critical node detection problem. Comput. Oper. Res. 43:261–270.Crossref, Google Scholar