Groupe d’études et de recherche en analyse des décisions

G-97-10

Cluster Analysis and Mathematical Programming

et

Given a set of entities, Cluster Analysis aims at finding subsets, called clusters, which are homogeneous and/or well separated. As many types of clustering and criteria for homogeneity or separation are of interest, this is a vast field. A survey is given from a mathematical programming viewpoint. Steps of a clustering study, types of clustering and criteria are discussed. Then algorithms for hierarchical, partitioning, sequential, additive and direct clustering are studied. Emphasis is on solution methods, i.e., dynamic programming, graph theoretical algorithm, branch-and-bound, cutting planes, column generation and heuristics.

, 36 pages