This paper considers the problem of partitioning the vertices of a weighted complete graph into cliques of unbounded size and number, such that the sum of the edge weights of all cliques is maximized. The problem is known as the clique-partitioning problem and arises as a clustering problem in qualitative data analysis. A simple greedy algorithm is extended to an ejection chain heuristic leading to optimal solutions in all practical test problems known from literature. The heuristic is used to compute an initial lower bound as well as to guide branching in a branch and bound algorithm which is superior to present exact methods. Empirical data for all three algorithms are reported. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.