An improved column generation algorithm for minimum sum-of-squares clustering

• 成果类型: Article
• 署名作者: Aloise, Daniel; Hansen, Pierre; Liberti, Leo
• 署名单位: Universidade Federal do Rio Grande do Norte; Universite de Montreal; HEC Montreal; Institut Polytechnique de Paris; Ecole Polytechnique
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0349-7
• 发表日期: 2012
• 页码: 195-220
• 关键词: global k-means; variable neighborhood search; cutting-plane method; branch; optimization

摘要

Given a set of entities associated with points in Euclidean space, minimum sum-of-squares clustering (MSSC) consists in partitioning this set into clusters such that the sum of squared distances from each point to the centroid of its cluster is minimized. A column generation algorithm for MSSC was given by du Merle et al. in SIAM Journal Scientific Computing 21:1485-1505. The bottleneck of that algorithm is the resolution of the auxiliary problem of finding a column with negative reduced cost. We propose a new way to solve this auxiliary problem based on geometric arguments. This greatly improves the efficiency of the whole algorithm and leads to exact solution of instances with over 2,300 entities, i.e., more than 10 times as much as previously done.