Groupe d’études et de recherche en analyse des décisions

G-2020-11

Computational study of a branching algorithm for the maximum \(k\)-cut problem

, et

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