A cutting plane algorithm for a clustering problem

In this paper the authors consider a clustering problem that arises in qualitative data analysis. This problem can be transformed to a combinatorial optimization problem, the clique partitioning problem. They have studied the latter problem from a polyhedral point of view and determined large classes of facets of the associated polytope. These theoretical results are utilized in this paper. The authors describe a cutting plane algorithm that is based on the simplex method and uses exact and heuristic separation routines for some of the classes of facets mentioned before. They discuss some details of the implementation of the present code and present their computational results. The authors mention applications from, e.g., zoology, economics, and the political sciences.