Journal
JOURNAL OF GLOBAL OPTIMIZATION
Volume 81, Issue 2, Pages 367-389Publisher
SPRINGER
DOI: 10.1007/s10898-021-00999-z
Keywords
Max-k-cut; Semidefinite relaxation; Branch-and-bound algorithm
Funding
- National Natural Science Foundation of China [11701177, 11771243]
- Fundamental Research Funds for the Central Universities [2018ZD14]
- University of Chinese Academy of Sciences
Ask authors/readers for more resources
The paper presents an efficient branch-and-bound algorithm to solve the max-k-cut problem, introducing a semidefinite relaxation method that is better suited for the framework. The algorithm utilizes the unique structure of the proposed relaxation and applies a branching method different from existing algorithms.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available