Mixed-integer models for complete-linkage clustering

Dendrograms are graphical representations of hierarchical clustering. Different definitions of the distance between two clusters in hierarchical clustering lead to different dendrograms. In this paper we focus on the dendrograms obtained when this distance is assumed to be the maximum of the distances between the elements of one cluster and the elements of the other cluster, known as complete-linkage dendrograms. For initial data where some elements are at the same distance as others, the number of different complete linkage dendrograms, which corresponds to the number of different ways to break ties for equal distances, can be large. We propose a system of linear inequalities whose set of solutions is the entire set of complete linkage dendrograms. Such a system of inequalities allows the inclusion of an objective function to select the best dendrogram among all these dendrograms according to some criteria, which may not be possible with classical dendrogram computation algorithms. We also adapt the system of inequalities to single-linkage dendrograms, where the distance between two clusters is the minimum distance between an element of one cluster and an element of the other cluster. The benefits of describing complete-linkage dendrograms through a system of inequalities are illustrated in a computational study in which five different objective functions are proposed.