Mixed integer linear programming formulation for K-means clustering problem

作     者：Agoston, Kolos Cs. E-Nagy, Marianna 

作者机构：Corvinus Univ Budapest Inst Operat & Dec Sci Budapest Hungary Corvinus Univ Budapest Corvinus Ctr Operat Res Budapest Hungary 

出 版 物：《CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH》 (Cent. Eur. J. Oper. Res.)

年 卷 期：2024年第32卷第1期

页      面：11-27页

核心收录：

学科分类：02[经济学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

基　　金：Corvinus University of Budapest 

主　　题：Mathematical programming Linear programming formulation Clustering K-means 

摘      要：The minimum sum-of-squares clusering is the most widely used clustering method. The minimum sum-of-squares clustering is usually solved by the heuristic KMEANS algorithm, which converges to a local optimum. A lot of effort has been made to solve such kind of problems, but a mixed integer linear programming formulation (MILP) is still missing. In this paper, we formulate MILP models. The advantage of MILP formulation is that users can extend the original problem with arbitrary linear constraints. We also present numerical results, we solve these models up to sample size of 150.