A distance-based point-reassignment heuristic for the k-hyperplane clustering problem

We consider the k-Hyperplane Clustering problem where, given a set of m points in R^n, we have to partition the set into k subsets (clusters) and determine a hyperplane for each of them, so as to minimize the sum of the square of the Euclidean distance between each point and the hyperplane of the corresponding cluster. We give a nonconvex mixed-integer quadratically constrained quadratic programming formulation for the problem. Since even very small-size instances are challenging for state-of-the-art spatial branch-and-bound solvers like Couenne, we propose a heuristic in which many critical points are reassigned at each iteration. Such points, which are likely to be ill-assigned in the current solution, are identified using a distance-based criterion and their number is progressively decreased to zero. Our algorithm outperforms the state-of-the-art one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest group of instances, we obtain an average improvement in the solution quality of 54%.