Group for Research in Decision Analysis

# Computational study of a branching algorithm for the maximum $$k$$-cut problem

## Vilmar Jefté Rodrigues De Sousa, Miguel F. Anjos, and Sébastien Le Digabel

This work considers the graph partitioning problem known as maximum k-cut. It focuses on investigating features of a branch-and-bound method to efficiently obtain global solutions. An exhaustive experimental study is carried out for two main components of a branch-and-bound algorithm: computing bounds and branching strategies. In particular, we propose the use of a variable neighborhood search heuristic to compute good feasible solutions, the k-chotomic strategy to split the problem, and a branching rule based on edge weight to select variables. Moreover, this work analyses the linear relaxation strengthened by semidefinite-based constraints, the cutting plane algorithm, and some node selection strategies. Computational results show that the method using the best procedures of the branch-and-bound outperforms the state-of-the-art and uncover the solution of several instances, especially for problems with $$k \geq 5$$.

, 25 pages