  The max-k-cut problem is to partition the vertices of a weighted graph $G =
(V,E)$ into $k\geq2$ 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$. 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 (new lower bounds) of most of the
tested instances. For the popular special case $k=2$ (i.e., the max-cut
problem), MOH also performs remarkably well by discovering 6 improved best
known results. We provide additional studies to shed light on the alternative
combinations of the employed search operators.
