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

Alberto Herrán

doi:10.1016/j.cor.2024.106946

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

2025-04-01

1

OA

AI

Maurício G. C. Resende

DOI：10.1016/j.cor.2024.106946

原文链接

查看原文

摘要

En 中文

The Multi-Constraint Graph Partitioning (MCGP) problem seeks a partition of the node set of a graph into 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 anew set of larger instances for the MCGP problem and provided detailed results for future comparisons.

Keyword:

Metaheuristics

Greedy Randomized Adaptive Search

Procedure

Graph partitioning

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

摘要

AI总结

期刊

机构