Resumen
The Multi-Constraint Graph Partitioning (MCGP) problem seeks a partition of the node set of a graph into a fixed number of clusters such that each cluster satisfies a collection of node-weight constraints and the total cost of the edges whose end nodes are in the same cluster is minimized. In this paper we propose a two-phase reactive GRASP heuristic to find near-optimal solutions to the MCGP problem. Our proposal is able to reach all the best known results for state-of-the-art instances, obtaining all the certified optimum values while spending only a fraction of the time in relation to the previous methods. To reach these results we have implemented an efficient computation method applied in the improvement phase. Besides, we have created a new set of larger instances for the MCGP problem and provided detailed results for future comparisons.
Alberto Herrán González
Profesor Titular de Universidad
J. Manuel Colmenar
Catedrático de Universidad
Mis intereses de investigación se centran en las metaheurísticas aplicadas a problemas de optimización. He trabajado en diferentes problemas de optimización combinatoria aplicando algoritmos trajectoriales como GRASP o VNS. Además, estoy muy interesado en las aplicaciones de la Evolución Gramatical, específicamente en el dominio de los modelos y la predicción, como alternativa a los enfoques de aprendizaje automático.