Detecting Critical Nodes in Sparse Graphs via “Reduce-Solve-Combine” Memetic Search

References

• Abbas K, Abbasi A, Shi D, Ling N, Yu L, Chen B, Cai S, Hasan Q (2021) Application of network link prediction in drug discovery. BMC Bioinformatics 22(1):187.Crossref, Google Scholar
• Addis B, Aringhieri R, Grosso A, Hosteins P (2016) Hybrid constructive heuristics for the critical node problem. Ann. Oper. Res. 238(1–2):637–649.Crossref, Google Scholar
• Aiex RM, Resende MG, Ribeiro CC (2007) TTT plots: A perl program to create time-to-target plots. Optim. Lett. 1(4):355–366.Crossref, Google Scholar
• Archetti C, Boland N, Speranza MG (2017) A matheuristic for the multivehicle inventory routing problem. INFORMS J. Comput. 29(3):377–387.Link, Google Scholar
• Aringhieri R, Grosso A, Hosteins P, Scatamacchia R (2016a) A general evolutionary framework for different classes of critical node problems. Engrg. Appl. Artificial Intelligence 55:128–145.Crossref, Google Scholar
• Aringhieri R, Grosso A, Hosteins P, Scatamacchia R (2016b) Local search metaheuristics for the critical node problem. Networks 67(3):209–221.Crossref, Google Scholar
• Arnold F, Santana Í, Sörensen K, Vidal T (2021) PILS: Exploring high-order neighborhoods by pattern mining and injection. Pattern Recognition 116:107957.Crossref, Google Scholar
• Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM (2009) Detecting critical nodes in sparse graphs. Comput. Oper. Res. 36(7):2193–2200.Crossref, Google Scholar
• Baggio A, Carvalho M, Lodi A, Tramontani A (2021) Multilevel approaches for the critical node problem. Oper. Res. 69(2):486–508.Link, Google Scholar
• Blum C, Davidson PP, López-Ibáñez M, Lozano JA (2016) Construct, merge, solve & adapt A new general algorithm for combinatorial optimization. Comput. Oper. Res. 68:75–88.Crossref, Google Scholar
• Boschetti MA, Maniezzo V (2022) Matheuristics: Using mathematics for heuristic design. 4OR 20(2):173–208.Crossref, Google Scholar
• Cai S, Su K, Sattar A (2011) Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artificial Intelligence 175(9–10):1672–1696.Crossref, Google Scholar
• Chen W, Jiang M, Jiang C, Zhang J (2020) Critical node detection problem for complex network in undirected weighted networks. Phys. A 538:122862.Crossref, Google Scholar
• Chen Y, Hao JK (2014) A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem. Eur. J. Oper. Res. 239(2):313–322.Crossref, Google Scholar
• Cooper WL, Homem-de-Mello T (2007) Some decomposition methods for revenue management. Transportation Sci. 41(3):332–353.Link, Google Scholar
• Cordeau J, Gaudioso M, Laporte G, Moccia L (2006) A memetic heuristic for the generalized quadratic assignment problem. INFORMS J. Comput. 18(4):433–443.Link, Google Scholar
• de Holanda Maia MR, Plastino A, Penna PHV (2020) Minereduce: An approach based on data mining for problem size reduction. Comput. Oper. Res. 122:104995.Crossref, Google Scholar
• de San Lázaro IM, Sánchez-Oro J, Duarte A (2021) Finding critical nodes in networks using variable neighborhood search. Mladenovic N, Sleptchenko A, Sifaleras A, Omar M, eds. Proc. Variable Neighborhood Search (Springer International Publishing, Cham, Switzerland), 1–13.Google Scholar
• Delgadillo FJD, Montiel O, Sepúlveda R (2016) Reducing the size of traveling salesman problems using vaccination by fuzzy selector. Expert Systems Appl. 49:20–30.Crossref, Google Scholar
• Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J. Machine Learn. Res. 7(1):1–30.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
• Doostmohammadian M, Rabiee HR, Khan UA (2020) Centrality-based epidemic control in complex social networks. Soc. Networks Anal. Mining 10(1):32.Crossref, Google Scholar
• Fu ZH, Hao JK (2015) Dynamic programming driven memetic search for the steiner tree problem with revenues, budget, and hop constraints. INFORMS J. Comput. 27(2):221–237.Link, Google Scholar
• Glover FW (1997) A template for scatter search and path relinking. Hao JK, Lutton E, Ronald EMA, Schoenauer M, Snyers D, eds. Proc. AE (Springer, Berlin), 1–51.Google Scholar
• Grahne G, Zhu J (2005) Fast algorithms for frequent itemset mining using fp-trees. IEEE Trans. Knowledge Data Engrg. 17(10):1347–1362.Crossref, Google Scholar
• Hao JK, Wu Q (2012) Improving the extraction and expansion method for large graph coloring. Discrete Appl. Math. 160(16–17):2397–2407.Crossref, Google Scholar
• Hopcroft J, Tarjan R (1973) Algorithm 447: Efficient algorithms for graph manipulation. Comm. ACM 16(6):372–378.Crossref, Google Scholar
• Hosteins P, Scatamacchia R, Grosso A, Aringhieri R (2022) The connected critical node problem. Theoretical Comput. Sci. 923:235–255.Crossref, Google Scholar
• Kenny A, Li X, Ernst AT (2018) A merge search algorithm and its application to the constrained pit problem in mining. Aguirre HE, Takadama K, eds. Proc. GECCO (ACM, New York), 316–323.Google Scholar
• Kenny A, Li X, Ernst AT, Sun Y (2019) An improved merge search algorithm for the constrained pit problem in open-pit mining. Proc. GECCO (ACM, New York), 294–302.Google Scholar
• Le HL, Neri F, Triguero I (2022) SPMS-ALS: A single-point memetic structure with accelerated local search for instance reduction. Swarm Evolution Comput. 69:100991.Crossref, Google Scholar
• Luna JM, Fournier-Viger P, Ventura S (2019) Frequent itemset mining: A 25 years review. Data Mining Knowledge Discovery 9(6):e1329.Crossref, Google Scholar
• Mihic K, Ryan K, Wood A (2018) Randomized decomposition solver with the quadratic assignment problem as a case study. INFORMS J. Comput. 30(2):295–308.Link, Google Scholar
• Montiel O, Delgadillo FJD, Sepúlveda R (2013) Combinatorial complexity problem reduction by the use of artificial vaccines. Expert Systems Appl. 40(5):1871–1879.Crossref, Google Scholar
• Mugisha S, Zhou HJ (2016) Identifying optimal targets of network attack by belief propagation. Phys. Rev. E 94:012305.Crossref, Google Scholar
• Nabli A, Carvalho M (2020) Curriculum learning for multilevel budgeted combinatorial problems. Adv. Neural Inform. Processing Systems 33:7044–7056.Google Scholar
• Naoum-Sawaya J, Buchheim C (2016) Robust critical node selection by benders decomposition. INFORMS J. Comput. 28(1):162–174.Link, Google Scholar
• Neri F, Cotta C (2012) Memetic algorithms and memetic computing optimization: A literature review. Swarm Evolution Comput. 2:1–14.Crossref, Google Scholar
• Nguyen DT, Shen Y, Thai MT (2013) Detecting critical nodes in interdependent power networks for vulnerability assessment. IEEE Trans. Smart Grid 4(1):151–159.Crossref, Google Scholar
• Plastino A, Barbalho H, Santos LFM, Fuchshuber R, Martins SL (2014) Adaptive and multi-mining versions of the DM-GRASP hybrid metaheuristic. J. Heuristics 20(1):39–74.Crossref, Google Scholar
• Pullan W (2015) Heuristic identification of critical nodes in sparse real-world graphs. J. Heuristics 21(5):577–598.Crossref, Google Scholar
• Purevsuren D, Cui G, Qu M, Win NH (2017) Hybridization of GRASP with exterior path relinking for identifying critical nodes in graphs. IAENG Internat. J. Comput. Sci. 44(2):157–165.Google Scholar
• Rezaei J, Zare-Mirakabad F, MirHassani SA, Marashi S (2021) EIA-CNDP: An exact iterative algorithm for critical node detection problem. Comput. Oper. Res. 127:105138.Crossref, Google Scholar
• Ribeiro MH, Plastino A, Martins SL (2006) Hybridization of GRASP metaheuristic with data mining techniques. J. Math. Modeling Algorithms 5(1):23–41.Crossref, Google Scholar
• Salemi H, Buchanan A (2022) Solving the distance-based critical node problem. INFORMS J. Comput. 34(3):1309–1326.Link, Google Scholar
• Schaap H, Schiffer M, Schneider M, Walther G (2022) A large neighborhood search for the vehicle routing problem with multiple time windows. Transportation Sci. 56(5):1369–1392.Link, Google Scholar
• Subramanyam A, Gounaris CE (2018) A decomposition algorithm for the consistent traveling salesman problem with vehicle idling. Transportation Sci. 52(2):386–401.Link, Google Scholar
• Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J. Sci. Comput. 1(2):146–160.Crossref, Google Scholar
• Thornton J, Pham DN, Bain S, Ferreira V Jr (2004) Additive vs. multiplicative clause weighting for SAT. McGuinness DL, Ferguson G, eds. Proc. AAAI, 191–196.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
• Ventresca M, Aleman D (2015) Efficiently identifying critical nodes in large complex networks. Comput. Soc. Networks 2(1):1–16.Crossref, Google Scholar
• Veremyev A, Boginski V, Pasiliao EL (2014a) Exact identification of critical nodes in sparse networks via new compact formulations. Optim. Lett. 8(4):1245–1259.Crossref, Google Scholar
• Veremyev A, Prokopyev OA, Pasiliao EL (2014b) An integer programming framework for critical elements detection in graphs. J. Combinatorial Optim. 28(1):233–273.Crossref, Google Scholar
• Veremyev A, Prokopyev OA, Pasiliao EL (2019) Finding critical links for closeness centrality. INFORMS J. Comput. 31(2):367–389.Link, Google Scholar
• Vitoriano B, Ortuño MT, Tirado G, Montero J (2011) A multi-criteria optimization model for humanitarian aid distribution. J. Global Optim. 51(2):189–208.Crossref, Google Scholar
• Wang Z, Di Y (2022) Cluster expansion method for critical node problem based on contraction mechanism in sparse graphs. IEICE Trans. Inform. Systems 105-D(6):1135–1149.Crossref, Google Scholar
• Wu Q, Hao JK (2012) Coloring large graphs based on independent set extraction. Comput. Oper. Res. 39(2):283–290.Crossref, Google Scholar
• Wu Q, Hao JK (2013) An extraction and expansion approach for graph coloring. Asia-Pacific J. Oper. Res. 30(5):1350018.Crossref, Google Scholar
• Wu Q, Wang Y, Glover F (2020) Advanced tabu search algorithms for bipartite boolean quadratic programs guided by strategic oscillation and path relinking. INFORMS J. Comput. 32(1):74–89.Link, Google Scholar
• Zhang Y, Mei Y, Zhang B, Jiang K (2021) Divide-and-conquer large scale capacitated arc routing problems with route cutting off decomposition. Inform. Sci. 553:208–224.Crossref, Google Scholar
• Zhang Y, Chen Q, Chen B, Liu J, Zheng H, Yao H, Zhang C (2020) Identifying hotspots of sectors and supply chain paths for electricity conservation in china. J. Clean Production 251:119653.Crossref, Google Scholar
• Zheng Y, Xue J (2010) A problem reduction based approach to discrete optimization algorithm design. Computing 88(1):31–54.Crossref, Google Scholar
• Zhou Y, Hao JK, Duval B (2022) Frequent pattern-based search: A case study on the quadratic assignment problem. IEEE Trans. Systems Man Cybernics Systems 52(3):1503–1515.Crossref, Google Scholar
• Zhou Y, Hao JK, Glover F (2019) Memetic search for identifying critical nodes in sparse graphs. IEEE Trans. Cybernetics 49(10):3699–3712.Crossref, Google Scholar
• Zhou Y, Kou Y, Zhou M (2023a) Bilevel memetic search approach to the soft-clustered vehicle routing problem. Transportation Sci. 57(3):701–716.Link, Google Scholar
• Zhou Y, Li J, Hao JK, Glover F (2023b) Detecting critical nodes in sparse graphs via “reduce-solve-combine” memetic search. http://dx.doi.org/10.1287/ijoc.2022.0130.cd, https://github.com/INFORMSJoC/2022.0130.Google Scholar
• Zhou Y, Wang Z, Jin Y, Fu ZH (2021a) Late acceptance-based heuristic algorithms for identifying critical nodes of weighted graphs. Knowledge Base. Systems 211:106562.Crossref, Google Scholar
• Zhou Y, Hao JK, Fu ZH, Wang Z, Lai X (2021b) Variable population memetic search: A case study on the critical node problem. IEEE Trans. Evolution Comput. 25(1):187–200.Crossref, Google Scholar
• Zhou Y, Kundu T, Qin W, Goh M, Sheu JB (2021c) Vulnerability of the worldwide air transportation network to global catastrophes such as covid-19. Transportation Res. Part E Logist. Transportation Rev. 154:102469.Crossref, Google Scholar
• Zhou Y, Wang G, Hao JK, Geng N, Jiang Z (2023c) A fast tri-individual memetic search approach for the distance-based critical node problem. Eur. J. Oper. Res. 308(2):540–554.Crossref, Google Scholar
• Zhou Y, Zhang X, Geng N, Jiang Z, Wang S, Zhou M (2023d) Frequent itemset-driven search for finding minimal node separators and its application to air transportation network analysis. IEEE Trans. Intelligent Transportation Systems 24(8):8348–8360.Google Scholar