A semidefinite relaxation based global algorithm for two-level graph partition problem
Junhao Wu, Cheng Zhu Lu, Shaoze Li, Zhibin Deng · Journal of Industrial and Management Optimization · 2022
In this paper, we design a new branch-and-bound algorithm to solve a variant of graph partition problem called two-level graph partition problem, which is arisen in mobile wireless communications. We first exploit the two-level structure of the problem, and propose a new semidefinite relaxation for the problem. Some valid constraints are derived to enhance the tightness of the semidefinite relaxation. Furthermore, we analyze the symmetric structure of the two-level graph partition problem, and propose an effective branch pruning rule to handle the symmetry. Based on the proposed semidefinite relaxation and the symmetry handing technique, a branch-and-bound algorithm is proposed. Our numerical results show that the proposed algorithm outperforms the existing linear integer programming based algorithm on two-level graph partition problems with high density.