A multiple search operator heuristic for the max-k-cut problem

The max-k-cut problem is to partition the vertices of an edge-weighted graph $$G = (V,E)$$ G = ( V , E ) into $$k\ge 2$$ k ≥ 2 disjoint subsets such that the weight sum of the edges crossing the different subsets is maximized. The problem is referred as the max-cut problem when $$k=2$$ k = 2 . In this work, we present a multiple operator heuristic (MOH) for the general max-k-cut problem. MOH employs five distinct search operators organized into three search phases to effectively explore the search space. Experiments on two sets of 91 well-known benchmark instances show that the proposed algorithm is highly effective on the max-k-cut problem and improves the current best known results (lower bounds) of most of the tested instances for $$k\in [3,5]$$ k ∈ [ 3 , 5 ] . For the popular special case $$k=2$$ k = 2 (i.e., the max-cut problem), MOH also performs remarkably well by discovering 4 improved best known results. We provide additional studies to shed light on the key ingredients of the algorithm.