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

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

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Number of pages20
JournalDiscrete Optimization
Early online date1 Jul 2021
Publication statusE-pub ahead of print - 1 Jul 2021


Dive into the research topics of 'Computational Study of a Branching Algorithm for the Maximum k-Cut Problem'. Together they form a unique fingerprint.

Cite this