Algoritmos Tabu Search em GPU para problemas de maximização de diversidade

Abstract

Combinatorial optimization problems, such as the Maximum Diversity Problem (MDP) and the Generalized Max-Mean Dispersion Problem (GMaxMeanDP), have been extensively studied due to their relevance in various practical applications, including web page classification, community mining, trust networks, group formation, resource allocation, and social network analysis. However, these problems face significant challenges when applied to large-scale in stances commonly encountered in real-world scenarios. Both MDP and GMaxMeanDP exhibit limitations with massive instances, primarily due to their reliance on matrix-based representations, which are inefficient for sparse data. Additionally, the execution of local search becomes increasingly time-consuming as the problem size grows, hindering the ability to obtain solutions within a feasible timeframe. This combination of structural inefficiency and growth in computational complexity compromises the effectiveness of conventional search strategies for large-scale problems. To overcome these limitations, this study proposes parallelized tabu search algorithms specifically designed to handle massive instances of both problems. The algorithms leverage the power of parallel processing on GPUs to significantly accelerate the local search process, enabling the efficient exploration of large solution spaces in less time. Moreover, the implementation of optimized data structures for representing sparse instances reduces memory overhead and enhances the scalability of the method. Experimental results demonstrate that GPU-based tabu search algorithms outperform state-of-the-art methods in the literature, both in terms of solution quality and execution time. This efficiency is particularly evident in large-scale instances, where the algorithms stand out as an effective and scalable alternative to address the challenges posed by combinatorial optimization problems in massive scenarios.