Breakout Local Search for the Max-Cutproblem

Given an undirected graph G=(V,E)G=(V,E) where each edge of E is weighted with an integer number, the maximum cut problem (Max-Cut) is to partition the vertices of V into two disjoint subsets so as to maximize the total weight of the edges between the two subsets. As one of Karp's 21 NP-complete problems, Max-Cut has attracted considerable attention over the last decades. In this paper, we present Breakout Local Search (BLS) for Max-Cut. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. The proposed algorithm shows excellent performance on the set of well-known maximum cut benchmark instances in terms of both solution quality and computational time. Out of the 71 benchmark instances, BLS is capable of finding new improved results in 34 cases and attaining the previous best-known result for 35 instances, within computing times ranging from less than 1 s to 5.6 h for the largest instance with 20,000 vertices.

► BLS is an effective Max-Cut algorithm based on iterated local search.
► BLS alternates between a descent phase and a dedicated diversification phase.
► Diversification is adapative and combines guided and random perturbations.
► BLS finds new record-breaking solutions for 33 out of 71 benchmark instances.
► The source code and the results of BLS is available online.