Metaheuristic approaches for ratio cut and normalized cut graph partitioning

Partitioning a set of graph vertices into two or more subsets constitutes an important class of problems in combinatorial optimization. Two well-known members of this class are the minimum ratio cut and the minimum normalized cut problems. Our focus is on developing metaheuristic-based approaches for ratio cut and normalized cut graph partitioning. We present three techniques in this category: multistart simulated annealing (MSA), iterated tabu search (ITS), and the memetic algorithm (MA). The latter two use a local search procedure. To speed up this procedure, we apply a technique that reduces the effort required for neighborhood examination. We carried out computational experiments on both random graphs and benchmark graphs from the literature. The numerical results indicate that the MA is a clear winner among the tested methods. Using rigorous statistical tests, we show that MA is unequivocally superior to MSA and ITS in terms of both the best and average solution values. Additionally, we compare the performances of MA and the variable neighborhood search (VNS) heuristic from the literature, which is the state-of-the-art algorithm for the normalized cut model. The experimental results demonstrate the superiority of MA over VNS, especially for structured graphs.