Abstract
Tabu search is a meta-heuristic that guides a local heuristic search procedure to explore the solution space beyond local optimality. One of the main components of tabu search is its use of adaptive memory, which creates an intelligent search pattern based on strategic choices, as opposed to random selections that are widely applied in other methodologies. Tabu search has connections with other memory-based methodologies, namely, scatter search and path relinking, and they have been extensively applied to many combinatorial optimization problems in general and in particular to several diversity models.
Memory-based strategies are the hallmark of tabu search approaches, founded on a quest for “integrating principles,” by which alternative forms of memory are appropriately combined with effective strategies for exploiting them. They are based on principles designed to cross boundaries of feasibility or local optimality, which were usually treated as barriers. The methods based on these principles constitute nowadays the area called adaptive memory programming. Over a wide range of problem settings, the strategic use of memory in these methods has proved to make dramatic differences in the ability to solve challenging problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aringhieri, R., Cordone, R., Melzani, Y.: Tabu search versus GRASP for the maximum diversity problem. 4OR 6(1), 45–60 (2008)
Brimberg, J., Mladenović, N., Urošević, D., Ngai, E.: Variable neighborhood search for the heaviest -subgraph. Comput. Oper. Res. 36(11), 2885–2891 (2009)
Duarte, A., Martí, R.: Tabu search and GRASP for the maximum diversity problem. Eur. J. Oper. Res. 178(1), 71–84 (2007)
Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8(1), 156–166 (1977)
Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986)
Glover, F., Hao, J.K.: Diversification-based learning in computing and optimization. J. Heurist. 25(4), 521–537 (2019)
Glover, F., Laguna, M.: Tabu search. In: Handbook of Combinatorial Optimization, pp. 2093–2229. Springer, Berlin (1998)
Glover, F., Kuo, C.C., Dhir, K.S.: Heuristic algorithms for the maximum diversity problem. J. Informat. Optim. Sci. 19(1), 109–132 (1998)
Glover, F., Kochenberger, G., **e, W., Luo, J.: Diversification methods for zero-one optimization. J. Heurist. 25(4), 643–671 (2019)
Glover, F., Campos, V., Martí, R.: Tabu search tutorial. A graph drawing application. Top 29(2), 319–350 (2021)
Kincaid, R.K.: Good solutions to discrete noxious location problems via metaheuristics. Ann. Oper. Res. 40(1), 265–281 (1992)
Kuby, M.J.: Programming models for facility dispersion: the p-dispersion and maxisum dispersion problems. Geograph. Analy. 19(4), 315–329 (1987)
Laguna, M., Martí, R.: Grasp and path relinking for 2-layer straight line crossing minimization. INFORMS J. Comput. 11(1), 44–52 (1999)
Macambira, E.M.: An application of tabu search heuristic for the maximum edge-weighted subgraph problem. Ann. Oper. Res. 117(1–4), 175–190 (2002)
Martí, R., Martínez-Gavara, A., Pérez-Peló, S., Sánchez-Oro, J.: Discrete diversity and dispersion maximization. a review and an empirical analysis from an or perspective. Eur. J. Oper. Res. 299(3), 795–813 (2022)
Palubeckis, G.: Iterated tabu search for the maximum diversity problem. Appl. Math. Comput. 189(1), 371–383 (2007)
Porumbel, D.C., Hao, J.K., Glover, F.: A simple and effective algorithm for the MaxMin diversity problem. Ann. Oper. Res. 186(1), 275–293 (2011)
Resende, M.G., Martí, R., Gallego, M., Duarte, A.: Grasp and path relinking for the max-min diversity problem. Comput. Oper. Res. 37(3), 498–508 (2010)
Wang, Y., Hao, J.K., Glover, F., Lü, Z.: A tabu search based memetic algorithm for the maximum diversity problem. Eng. Appl. Artif. Intell. 27, 103–114 (2014)
Zhou, Y., Hao, J.K., Duval, B.: Opposition-based memetic search for the maximum diversity problem. IEEE Trans. Evolut. Comput. 21(5), 731–745 (2017)
Acknowledgements
This research has been partially supported by the Ministerio de Ciencia e Innovación of Spain (Grant Ref. PID2021-125709OB-C21) funded by MCIN/ AEI/ 10.13039/ 501100011033/ FEDER, UE. It has been also supported by the Generalitat Valenciana (Grant Ref. CIAICO/2021/224).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Martí, R., Martínez-Gavara, A., Glover, F. (2023). Tabu Search. In: Martí, R., Martínez-Gavara, A. (eds) Discrete Diversity and Dispersion Maximization. Springer Optimization and Its Applications, vol 204. Springer, Cham. https://doi.org/10.1007/978-3-031-38310-6_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-38310-6_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-38309-0
Online ISBN: 978-3-031-38310-6
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)