  We consider a variant of the clustering problem for a complete weighted
graph. The aim is to partition the nodes into clusters maximizing the sum of
the edge weights within the clusters. This problem is known as the clique
partitioning problem, being NP-hard in the general case of having edge weights
of different signs. We propose a new method of estimating an upper bound of the
objective function that we combine with the classical branch-and-bound
technique to find the exact solution. We evaluate our approach on a broad range
of random graphs and real-world networks. The proposed approach provided
tighter upper bounds and achieved significant convergence speed improvements
compared to known alternative methods.
