Branch‐and‐Bound Algorithms for the KK‐Cluster Problem Based on SDP Bounds Evaluated by Lagrangian Relaxation

In this paper, we introduce new Semidefinite Programming (SDP) dual bounding procedures and two Branch‐and‐bound algorithms based on them, BBLAG and BBLAG+ , for solving the ‐Cluster Problem, KCP. The algorithms compute Lagrangian relaxation SDP bounds by relaxing the positive semidefiniteness constraint and attaching conveniently defined matrices of Lagrangian multipliers to it. Operating under a more standard approach found in the literature, BBLAG only requires the matrix of Lagrangian multipliers to be positive semidefinite; symmetry is not required. BBLAG+ , on the other hand, enforces both conditions and, as a result, solves a reformulation of the Lagrangian Dual problem without the need of projecting the matrix of Lagrangian multipliers onto the cone of symmetric positive semidefinite matrices. The positive impact of avoiding the projection step is tremendous, as it is the most CPU time‐consuming operation involved in the computation of our SDP bounds, by means of Lagrangian Relaxation. Because of that, BBLAG+ is four times faster than BBLAG . Additionally, BBLAG+ attained quite competitive results when compared to the existing KCP algorithms from the literature, BiqCrunch and BiqBin , that also rely on SDP bounds. In practice, the SDP bounds computed by BBLAG+ neither dominate nor are dominated by the SDP bounds computed by its competitors. For the densest subgraph problem, one of the five KCP variants tested here, the best results were provided by BiqCrunch followed by BiqBin . For four other sets of KCP instances, BBLAG+ usually provides better results than BiqCrunch and BiqBin , for a wide range of values of and graph densities. In summary, BBLAG+ seems to be a robust approach for a wide range of KCP instances.