A hybridization between memetic algorithm and semidefinite relaxation for the max-cut problem

Abstract

The Max-Cut problem is a classical NP-hard combinatorial optimization problem. It consists of dividing the vertices of a weighted graph into two subsets, such that the sum of the weights of the edges connecting the two subsets is maximized. Although semidefinite relaxation algorithms for Max-Cut have been proved to be of high quality and offer performance guarantees, in practice, metaheuristic algorithms are still the first option to solve large Max-Cut instances. In this paper, we present the first effort at combining semidefinite programming (SDP) with metaheuristic algorithm (Memetic Algorithm) to solve the Max-Cut problem. Based on the solution of semidefinite relaxation, we use Goemans-Williamson Algorithm to seed high quality solutions to the initial population for the memetic algorithm. Experimental results on well-known benchmark problems show that our new hybrid algorithm is capable of obtaining better solutions in the initial population generation stage than previous algorithms, and the overall performance of our algorithm is better than one of the best existing algorithms. Besides, new best solutions for 14 benchmark problems were found by our algorithm. © 2012 ACM.