An Exact Solution Approach for Hierarchical Clustering

In hierarchical clustering, a hierarchy of nested data partitions is obtained. Commonly used agglomerative and divisive heuristics do not optimize over a global objective function. Although several objective functions and approximation algorithms have been proposed, exact methods that find optimal solutions based on these objective functions have received little attention. In this paper, we consider an objective function involving a sum of partitional clustering objectives over each level. We introduce two compact mixed-integer linear programming formulations as well as a set-covering formulation that can handle various objective functions. In addition, we provide a branch-and-price framework to solve the set-covering formulation. We apply our branch-and-price approach to real-world data instances containing up to 200 observations compared with 15 in the literature. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0903 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0903 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .