A cutting plane algorithm for a clustering problem. (English) Zbl 0675.90072

Summary: 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.


90C27 Combinatorial optimization
52Bxx Polytopes and polyhedra
62H30 Classification and discrimination; cluster analysis (statistical aspects)
90C90 Applications of mathematical programming


Full Text: DOI


[1] 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. · Zbl 0646.90084
[2] J.P. Barthélemy and B. Monjardet, ”The median procedure in cluster analysis and social choice theory,”Mathematical Social Sciences 1 (1981) 235–267. · Zbl 0486.62057
[3] J.A. Bondy and U.S.R. Murty,Graph Theory with Applications (Macmillan, London, 1976). · Zbl 1226.05083
[4] S. Chah, ”Classification of heterogeneous data: micro computers,” Paper presented at the III International Symposium on Data Analysis (Brussels, 1985).
[5] H.P. Crowder and M.W. Padberg, ”Solving large scale travelling salesman problems to optimality,”Management Science 26 (1980) 495–509. · Zbl 0444.90068
[6] M. Grötschel, L. Lovász and A. Schrijver, ”The ellipsoid method and its consequences in combinatorial optimization”,Combinatorica 1 (1981) 169–197. · Zbl 0492.90056
[7] M. Grötschel, M. Jünger and G. Reinelt, ”A cutting plane algorithm for the linear ordering problem”,Operations Research 32 (1984) 1195–1220. · Zbl 0554.90077
[8] M. Grötschel and O. Holland, ”Solving matching problems with linear programming,”Mathematical Programming 33 (1985) 243–259. · Zbl 0579.90069
[9] 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. · Zbl 0715.90092
[10] J.A. Hartigan,Clustering Algorithms (Wiley, New York, 1975). · Zbl 0372.62040
[11] J.F. Marcotorchino,Agrégation des Similarités en Classification Automatique, These de Doctorat d’état (Université Paris vi, 1981).
[12] 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. · Zbl 0485.62002
[13] 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). · Zbl 0457.90010
[14] J.F. Marcotorchino and P. Michaud, ”Heuristic approach to the similarity aggregation problem,”Methods of Operations Research 43 (1981b) 395–404. · Zbl 0505.90002
[15] O. Opitz and M. Schader, ”Analyse qualitativer Daten: Einführung und Übersicht,”Operations Research Spektrum 6 (1984) 67–83. · Zbl 0536.90047
[16] 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. · Zbl 0618.90082
[17] G. Reinelt,The Linear Ordering Problem: Algorithms and Applications (Research and Exposition in Mathematics 8) (Helderman Verlag, Berlin, 1985). · Zbl 0565.68058
[18] M. Schader and U. Tüshaus, ”Ein Subgradientenverfahren zur Klassifikation qualitativer Daten,”Operations Research Spektrum 7 (1985) 1–5. · Zbl 0556.90055
[19] A. Schrijver,Theory of Linear and Integer Programming (Wiley, Chichester, UK, 1986). · Zbl 0665.90063
[20] 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.
[21] U. Tüshaus, ”Aggregation binärer Relationen in der qualitativen Datenanalyse,” in:Mathematical Systems in Economics Vol 82 (Hain, Königstein, 1983). · Zbl 0525.62003
[22] 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.
[23] 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.
[24] Y. Wakabayashi,Aggregation of Binary Relations: Algorithmic and Polyhedral Investigations, Ph.D. Thesis (Universität Augsburg, West Germany, 1986). · Zbl 0606.68036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.