An Exact Solution Approach for Hierarchical Clustering
提出层次聚类的精确优化方法，包括混合整数线性规划和集合覆盖模型，并用分支定价算法求解，在多达200个观测值的数据集上验证，远超文献中的15个。
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/ .