We study in this paper the application of simulated annealing and tabu search in the solution of the clique partitioning problem. We illustrate the effectiveness of these techniques by computational results associated not only with randomly generated problems, but also with real-life problems arising from applications concerning the optimal aggregation of binary relations into an equivalence relation. The interest for these approaches is emphasized by the exhibition of a special class of instances of the clique partitioning problem for which the most commonly used heuristics are proved to perform arbitrarily bad, while tabu search systematically obtains the optimal solution.