Less is more: basic variable neighborhood search heuristic for balanced minimum sum-of-squares clustering

Abstract

Clustering addresses the problem of finding homogeneous and well-separated subsets, called clusters, from a set of given data points. In addition to the points themselves, in many applications, there may exist constraints regarding the size of the clusters to be found. Particularly in balanced clustering, these constraints impose that the entities be equally spread among the different clusters. In this work, we present a basic variable neighborhood search heuristic for balanced minimum sum-of-squares clustering, following the recently proposed “Less Is More Approach”. Computational experiments and statistical tests show that the proposed algorithm outperforms the current state-of-the-art algorithm for the problem, indicating that non sophisticated and easy to implement metaheuristic methods can be sufficient to produce successful results in practice.