Two-phase GRASP for the Multi-Constraint Graph Partitioning problem
Fecha
2025-04
Título de la revista
ISSN de la revista
Título del volumen
Editor
Elsevier
Enlace externo
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
Descripción
The authors would like to thank Ramiro Torres, Diego Recalde and Polo Vaca for kindly providing their code and instances from Recalde et al. (2020).
This work has been partially supported by the Spanish Ministerio de Ciencia e Innovación (MCIN/AEI/10.13039/501100011033) under grant ref. PID2021-126605NB-I00 and by ERDF A way of making Europe; and Generalitat Valenciana with grant ref. CIAICO/2021/224.
Palabras clave
Citación
Alberto Herrán, J. Manuel Colmenar, Mauricio G.C. Resende, Two-phase GRASP for the Multi-Constraint Graph Partitioning problem, Computers & Operations Research, Volume 176, 2025, 106946, ISSN 0305-0548, https://doi.org/10.1016/j.cor.2024.106946
Colecciones

Excepto si se señala otra cosa, la licencia del ítem se describe como Attribution 4.0 International