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

Cheng Lu and Zhibin Deng ()
Additional contact information
Cheng Lu: North China Electric Power University
Zhibin Deng: University of Chinese Academy of Sciences

Journal of Global Optimization, 2021, vol. 81, issue 2, No 5, 367-389

Abstract: Abstract 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.

Keywords: Max-k-cut; Semidefinite relaxation; Branch-and-bound algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-00999-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:81:y:2021:i:2:d:10.1007_s10898-021-00999-z

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-00999-z

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().