Tabu search: an application to the minimum dominating set problem

• J. Manuel Colmenar ^[1] ; Manuel Laguna ^[2] ; Raúl Martín-Santamaría ^[1]
  1. [1] Universidad Rey Juan Carlos,Móstoles, Madrid, Spain
  2. [2] University of Colorado Boulder,USA
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. Extra 2, 2025 (Ejemplar dedicado a: Metaheuristics), págs. 304-326
• Idioma: inglés
• DOI: 10.1007/s11750-025-00697-z
• Enlaces
  • Texto completo
• Resumen

  • Tabu Search is a metaheuristic renowned for its ability to navigate complex solution spaces by iteratively exploring neighborhoods and intelligently diversifying the search process to avoid getting trapped in local optima. We describe the main elements of the tabu search methodology in the context of finding high-quality solutions to the minimum dominating set problem (MDSP). The MDSP is a fundamental combinatorial optimization challenge with applications in various fields, including network design, social network analysis, and bioinformatics.

• Referencias bibliográficas
  • Albareda-Sambola M, Fernández E, Saldanha-da-Gama F (2017) Heuristic solutions to the facility location problem with general Bernoulli demands....
  • Casado A, Bermudo S, López-Sánchez AD, Sánchez-Oro J (2023) An iterated greedy algorithm for finding the minimum dominating set in graphs....
  • Cavero S, Pardo EG, Glover F, Martí R (2024a) Strategic oscillation tabu search for improved hierarchical graph drawing. Expert Syst Appl...
  • Cavero S, Pardo EG, Glover F, Martí R (2024b) Strategic oscillation tabu search for improved hierarchical graph drawing. Expert Syst Appl...
  • Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8:156–166
  • Glover F (1990) Tabu search-part II. ORSA J Comput 2(1):4–32. https://doi.org/10.1287/ijoc.2.1.4
  • Glover F, Hao J-K (2011) The case for strategic oscillation. Ann Oper Res 183:163–173
  • Glover F, Campos V, Martí R (2021) Tabu search tutorial: a graph drawing application. TOP 29:319–350. https://doi.org/10.1007/s11750-021-00605-1
  • González MA, Palacios JJ, Vela CR, Hernández-Arauzo A (2017) Scatter search for minimizing weighted tardiness in a single machine scheduling...
  • Hanafi S, Fréville A (2001) Extension of reverse elimination method through a dynamic management of the tabu list. RAIRO Oper Res 35(2):251–267
  • Lai X, Hao J-K, Yue D (2019) Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem. Eur J Oper Res 274(1):35–48
  • Lu Z, Martínez-Gavara A, Hao J-K, Lai X (2023) Solution-based tabu search for the capacitated dispersion problem. Expert Syst Appl 223:119856....
  • Martí R, Martínez-Gavara A, Glover F (2023) In: Martí R, Martínez-Gavara A (eds) Tabu search. Springer, Cham, pp 137–149. https://doi.org/10.1007/978-3-031-38310-6_7
  • Martín-Santamaría R, Cavero S, Herrán A, Duarte A, Colmenar JM (2024a) A practical methodology for reproducible experimentation: an application...
  • Martín-Santamaría R, López-Ibáñez M, Stützle T, Colmenar JM (2024b) On the automatic generation of metaheuristic algorithms for combinatorial...
  • Mottaki N, Motameni H, Mohamadi H (2023) An effective hybrid genetic algorithm and tabu search for maximizing network lifetime using coverage...
  • Muritiba AEF, Gomes MJN, Souza MF, Oria HLG (2022) Path-relinking with tabu search for the capacitated centered clustering problem. Expert...
  • Pacheco JA, Casado S (2023) A stepped tabu search method for the clique partitioning problem. Appl Intell 53:16275–16292. https://doi.org/10.1007/s10489-022-04304-7
  • Pacheco J, Saiz O, Casado S, Ubillos S (2023) A multistart tabu search-based method for feature selection in medical applications. Sci Rep...
  • Peng B, Wang S, Liu D, Su Z, Lü Z, Glover F (2024) Solving the incremental graph drawing problem by multiple neighborhood solution-based tabu...
  • Ríos-Mercado RZ, González-Velarde JL, Maldonado-Flores JR (2023) Tabu search with strategic oscillation for improving collection assignment...
  • Sánchez-Oro J, López-Sánchez A, Hernández-Díaz AG, Duarte A (2022) GRASP with strategic oscillation for the α-neighbor p-center problem. Eur...
  • Shao W, Xiao T, Su Z, Ding J, Lü Z (2023) A hybridization of granular adaptive tabu search with path relinking for the multi-depot open vehicle...
  • Shelbourne BC, Battarra M, Potts CN (2017) The vehicle routing problem with release and due dates. INFORMS J Comput 4:705–723
  • Tagne Fute E, Nyabeye Pangop D, Tonye E (2023) A new hybrid localization approach in wireless sensor networks based on particle swarm optimization...
  • Wei Z, Hao J-K (2021) Multistart solution-based tabu search for the set-union knapsack problem. Appl Soft Comput 105:107260. https://doi.org/10.1016/j.asoc.2021.107260
  • Zhou H, Liu H, Lv C, Zhang C, ShenW (2024) A path relinking with tabu search algorithm for solving hybrid flow shop scheduling problem considering...
  • Zou Y, Hao J-K, Wu Q (2024) A reinforcement learning guided hybrid evolutionary algorithm for the latency location routing problem. Comput...