Abstract
In this paper we consider a clustering problem that arises in qualitative data analysis. This problem can be transformed to a combinatorial optimization problem, the clique partitioning problem. We 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. We 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. We discuss some details of the implementation of our code and present our computational results. We mention applications from, e.g., zoology, economics, and the political sciences.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, “An application of combinatorial optimization to statistical physics and circuit layout design,”Operations Research 36 (1988) 493–513.
J.P. Barthélemy and B. Monjardet, “The median procedure in cluster analysis and social choice theory,”Mathematical Social Sciences 1 (1981) 235–267.
J.A. Bondy and U.S.R. Murty,Graph Theory with Applications (Macmillan, London, 1976).
S. Chah, “Classification of heterogeneous data: micro computers,” Paper presented at the III International Symposium on Data Analysis (Brussels, 1985).
H.P. Crowder and M.W. Padberg, “Solving large scale travelling salesman problems to optimality,”Management Science 26 (1980) 495–509.
M. Grötschel, L. Lovász and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization“,Combinatorica 1 (1981) 169–197.
M. Grötschel, M. Jünger and G. Reinelt, “A cutting plane algorithm for the linear ordering problem“,Operations Research 32 (1984) 1195–1220.
M. Grötschel and O. Holland, “Solving matching problems with linear programming,”Mathematical Programming 33 (1985) 243–259.
M. Grötschel and Y. Wakabayashi, “Facets of the clique partitioning polytope”, Report No. 6, Schwerpunktprogramm der Deutschen Forschungsgemeinschaft Universität Augsburg (Augsburg, West Germany, 1987), to appear inMathematical Programming.
J.A. Hartigan,Clustering Algorithms (Wiley, New York, 1975).
J.F. Marcotorchino,Agrégation des Similarités en Classification Automatique, These de Doctorat d'état (Université Paris vi, 1981).
J.F. Marcotorchino and P. Michaud, “Optimisation en analyse des données relationnelles,” in: E. Diday, et al. (eds.),Data Analysis and Informatics (North-Holland, Amsterdam, 1980) pp. 655–670.
J.F. Marcotorchino and P. Michaud, “Optimization in exploratory data analysis,” Proceedings of 5th International Symposium on Operations Research 1981 (Physica Verlag, Köln, 1981a).
J.F. Marcotorchino and P. Michaud, “Heuristic approach to the similarity aggregation problem,”Methods of Operations Research 43 (1981b) 395–404.
O. Opitz and M. Schader, “Analyse qualitativer Daten: Einführung und Übersicht,”Operations Research Spektrum 6 (1984) 67–83.
M. Padberg and G. Rinaldi, “Optimization of a 532-city symmetric traveling salesman problem by branch and cut,”Operations Research Letters 6 (1987) 1–7.
G. Reinelt,The Linear Ordering Problem: Algorithms and Applications (Research and Exposition in Mathematics 8) (Helderman Verlag, Berlin, 1985).
M. Schader and U. Tüshaus, “Ein Subgradientenverfahren zur Klassifikation qualitativer Daten,”Operations Research Spektrum 7 (1985) 1–5.
A. Schrijver,Theory of Linear and Integer Programming (Wiley, Chichester, UK, 1986).
H. Späth, “Partitionierende Cluster-Analyse für große Objektmengen mit binären Merkmalen am Beispiel von Firmen und deren Berufsgruppenbedarf,” in: H. Späth, (ed.),Fallstudien Cluster Analyse (Oldenburg, München, 1977) pp. 63–80.
U. Tüshaus, “Aggregation binärer Relationen in der qualitativen Datenanalyse,” in:Mathematical Systems in Economics Vol 82 (Hain, Königstein, 1983).
UNO, “Resolutions and Decisions adopted by the General Assembly during the first part of its thirty-ninth Session” (from Sept. 18 to Dec. 18, 1984), (1985) 412–419.
G. Vescia, (a) “Descriptive classification of cetacea: whales, porpoises and dolphins,” (b) “Automatic classification of cetaceans by similarity aggregation,” in: J.F. Marcotorchino, J.M. Proth and J. Janssen, (eds.),Data Analysis in Real Life Environment: Ins and Outs of Solving Problems (Elsevier Science Publishers B.V. (North-Holland, Amsterdam, 1985) pp. 7–24.
Y. Wakabayashi,Aggregation of Binary Relations: Algorithmic and Polyhedral Investigations, Ph.D. Thesis (Universität Augsburg, West Germany, 1986).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Grötschel, M., Wakabayashi, Y. A cutting plane algorithm for a clustering problem. Mathematical Programming 45, 59–96 (1989). https://doi.org/10.1007/BF01589097
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01589097