Búsqueda de Vecindad Variable secuencial y paralela: una aplicación al problema de la maximización del corte

Abstract

En este trabajo se propone un análisis comparativo de la implementación paralela y secuencial de un algoritmo basado en el es-quema Variable Neighborhood Search. La paralelización se lleva a cabo utilizando NVIDIA CUDA sobre GPU. Para ilustrar el comportamiento de ambas propuestas se utiliza el problema de la maximización del corte (MaxCut Problem -MCP). Dado un grafo G no dirigido, se define un corte como la división del conjunto de vértices de G en dos subconjuntos S y S ′ de forma que S ′ = V S. El MCP consiste entonces en encontrar el corte de máximo valor en G de entre todos los posibles. Para resolver dicho problema se propone un esquema basado en la estrategia Basic VNS. La paralelización se aplica a la búsqueda local, analizando las di-ferencias entre la búsqueda local paralela y la secuencial. Los resultados obtenidos muestran como la paralelización de la búsqueda local en GPU consigue reducir en gran medida el tiempo de ejecución, proporcionando soluciones de mayor calidad. 1. Introducción Se define un grafo G = (V, E), con n = |V | y m = |E|, como un conjunto de vértices V y el conjunto de aristas que los unen E. Siendo w ij el peso asociado con la arista (i, j) ∈ E, se define un corte(S, S ′) como la división de V en dos conjuntos S y S ′ = V S. El valor de dicho corte se calcula mediante la expresión corte(S, S ′) =

Jesús Sánchez-Oro

Associate Professor

Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.

Abraham Duarte

Full Professor

Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.