Computational Study of a Branching Algorithm for the Maximum k-Cut Problem

This work considers the graph partitioning problem known as maximumk-cut.It focuses on investigating features of a branch-and-bound method to obtainglobal solutions. An exhaustive experimental study is carried out for the two maincomponents of a branch-and-bound algorithm: Computing bounds and branchingstrategies. In particular, we propose the use of a variable neighborhood searchmetaheuristic to compute good feasible solutions, thek-chotomic strategy to splitthe problem, and a branching rule based on edge weights to select variables. More-over, we analyze a linear relaxation strengthened by semidefinite-based constraints,a cutting plane algorithm, and node selection strategies. Computational resultsshow that the resulting method outperforms the state-of-the-art approach anddiscovers the solution of several instances, especially for problems withk≥5.