Two-phase GRASP for the Multi-Constraint Graph Partitioning problem

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.

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
license logo
Excepto si se señala otra cosa, la licencia del ítem se describe como Attribution 4.0 International