A branch-and-bound algorithm for solving max-k-cut problem

摘要

The max-k-cut problem is one of the most well-known combinatorial optimization problems. In this paper, we design an efficient branch-and-bound algorithm to solve the max-k-cut problem. We propose a semidefinite relaxation that is as tight as the conventional semidefinite relaxations in the literature, but is more suitable as a relaxation method in a branch-and-bound framework. We then develop a branch-and-bound algorithm that exploits the unique structure of the proposed semidefinite relaxation, and applies a branching method different from the one commonly used in the existing algorithms. The symmetric structure of the solution set of the max-k-cut problem is discussed, and a strategy is devised to reduce the redundancy of subproblems in the enumeration procedure. The numerical results show that the proposed algorithm is promising. It performs better than Gurobi on instances that have more than 350 edges, and is more efficient than the state-of-the-art algorithm bundleBC on certain types of test instances.