Clustering and clique partitioning: Simulated annealing and tabu search approaches |
| |
Authors: | Saul G. de Amorim Jean-Pierre Barthélemy Celso C. Ribeiro |
| |
Affiliation: | (1) Catholic University of Rio de Janeiro, Caixa Postal 38063, 22452 Rio de Janeiro, Brazil;(2) Ecole Nationale Supérieure des Télécommunications, 75634 Paris Cedex 13, France;(3) Department of Computer Science, Catholic University of Rio de Janeiro, 22453 Rio de Janeiro, Brazil |
| |
Abstract: | We study the application of simulated annealing and tabu search to the solution of the clique partitioning problem. We illustrate the effecveness 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 need for these approaches is emphasized by the example of a special class of instances of the clique partitioning problem for which the most commonly used heuristics perform arbitrarily badly, while tabu search systematically obtains the optimal solution. Résumé Nous étudions dans cet article l'application du recuit simulé et de la méthode de recherche tabou dans la résolution du problème de partitionnement de graphes en cliques. Nous illustrons l'efficacité de ces techniques par des résultats numériques associés soit à des problèmes génerés au hasard, soit à des problèmes réels concernant l'agrégation de relations binaires dans une relation d'équivalence. L'intérêt de ces approches est mis en évidence à travers une classe de problèmes pour lesquels les heuristiques les plus connues ont une performance arbitrairement mauvaise, tandis que la méthode de recherche tabou obtient systématiquement des solutions optimales. |
| |
Keywords: | Clustering Binary relations Equivalence relation Cliques Combinatorial optimization Heuristics Simulated annealing Tabu search |
本文献已被 SpringerLink 等数据库收录! |
|