Abstract: The clique partitioning problem (CPP)is a much-studied and NP-hard combinatorial optimisation problem. We are given a complete undirected graph comprising of nodes and edges that have weights. The task is to partition this graph into subsets (i.e., cliques), such that the sum of the weights of the edges that have both end-vertices in the same subset is maximised. The CPP has many applications in data mining, image processing and structure detection in networks. We propose two new solution methods to this problem. One is a heuristic based on very large scale neighbourhood search and the other is an exact method using cutting-plane techniques.