A GPU-Based Tabu Search Algorithm for Large Instances of the Generalized Max-Mean Dispersion Problem
Resumo
O Problema de Dispersão Máxima Média Ponderada (GMaxMeanDP) é importante em áreas como classificação de páginas web, mineração de comunidades e análise de redes sociais. No entanto, os métodos atuais para esse problema enfrentam desafios em instâncias de grande escala, principalmente devido a ineficiências de memória em suas representações matriciais e ao crescente tempo computacional necessário para executá-los. Este estudo propõe um algoritmo de busca tabu paralelizado, utilizando GPUs para acelerar a busca local e estruturas de dados otimizadas para reduzir a sobrecarga de memória. Testes em instâncias de 2.000 a 20.000 vértices mostram que o algoritmo supera os métodos existentes na literatura em termos de qualidade das soluções e tempo de execução, sendo uma solução eficaz e escalável para cenários massivos.Referências
Carrasco, R. et al. (2015). Tabu search for the max-mean dispersion problem. Knowledge Based System, 85:256–264.
Essaid, M., Idoumghar, L., Lepagnot, J., and Brevilliers, M. (2019). Gpu parallelization strategies for metaheuristics: a survey. International Journal of Parallel, Emergent and Distributed Systems, 34(5):497–522.
Glover, F. W. and Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers, Dordrecht.
Kerchove, C. and Dooren, P. V. (2008). The page trust algorithm: How to rank web pages when negative links are allowed? pages 346–352.
Lai, X., Hao, J.-K., and Glover, F. (2020). A study of two evolutionary/tabu search approaches for the generalized max-mean dispersion problem. Expert Systems with Applications, 139:112856.
Nogueira, B., Rosendo, W., Tavares, E., and Andrade, E. (2024). Gpu tabu search: a study on using gpu to solve massive instances of the maximum diversity problem. Journal of Parallel and Distributed Computing, page 105012.
Nosferalatu (2020). A simple gpu hash table. [link].
Prokopyev, O. A., Kong, N., and Martinez-Torres, D. L. (2009). The equitable dispersion problem. European Journal of Operational Research, 197(1):59–67.
Wilt, N. (2013). The CUDA Handbook: A Comprehensive Guide to GPU Programming. Pearson Education.
Yang, B., Cheung, W., and Liu, J. (2007). Community mining from signed social networks. IEEE Transactions on Knowledge & Data Engineering, 19(10):1333–1348.
Zhao, J., Hifi, M., and Latrem, K. (2024). Hybrid particle swarm optimization and skewed variable neighborhood search techniques for the generalized max-mean dispersion problem.
Zhou, Y., Hao, J.-K., and Duval, B. (2017). Opposition-based memetic search for the maximum diversity problem. IEEE Transactions on Evolutionary Computation, 21(5):731–745.
Essaid, M., Idoumghar, L., Lepagnot, J., and Brevilliers, M. (2019). Gpu parallelization strategies for metaheuristics: a survey. International Journal of Parallel, Emergent and Distributed Systems, 34(5):497–522.
Glover, F. W. and Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers, Dordrecht.
Kerchove, C. and Dooren, P. V. (2008). The page trust algorithm: How to rank web pages when negative links are allowed? pages 346–352.
Lai, X., Hao, J.-K., and Glover, F. (2020). A study of two evolutionary/tabu search approaches for the generalized max-mean dispersion problem. Expert Systems with Applications, 139:112856.
Nogueira, B., Rosendo, W., Tavares, E., and Andrade, E. (2024). Gpu tabu search: a study on using gpu to solve massive instances of the maximum diversity problem. Journal of Parallel and Distributed Computing, page 105012.
Nosferalatu (2020). A simple gpu hash table. [link].
Prokopyev, O. A., Kong, N., and Martinez-Torres, D. L. (2009). The equitable dispersion problem. European Journal of Operational Research, 197(1):59–67.
Wilt, N. (2013). The CUDA Handbook: A Comprehensive Guide to GPU Programming. Pearson Education.
Yang, B., Cheung, W., and Liu, J. (2007). Community mining from signed social networks. IEEE Transactions on Knowledge & Data Engineering, 19(10):1333–1348.
Zhao, J., Hifi, M., and Latrem, K. (2024). Hybrid particle swarm optimization and skewed variable neighborhood search techniques for the generalized max-mean dispersion problem.
Zhou, Y., Hao, J.-K., and Duval, B. (2017). Opposition-based memetic search for the maximum diversity problem. IEEE Transactions on Evolutionary Computation, 21(5):731–745.
Publicado
20/07/2025
Como Citar
ROSENDO, William; ANDRADE, Ermeson; NOGUEIRA, Bruno.
A GPU-Based Tabu Search Algorithm for Large Instances of the Generalized Max-Mean Dispersion Problem. In: SEMINÁRIO INTEGRADO DE SOFTWARE E HARDWARE (SEMISH), 52. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 501-512.
ISSN 2595-6205.
DOI: https://doi.org/10.5753/semish.2025.9110.
