An Adaptive Point-Reassignment Metaheuristic for the k-Hyperplane Clustering Problem

The k-Hyperplane Clustering problem is that of, given a set of m points {a1, . . . , am} in Rn, determining k hyperplanes Hj = {a ∈ R n | w T j a = γj , wj ∈ R n, γj ∈ R}, with 1 ≤ j ≤ k, and assigning each point to a hyperplane so as to minimize the sum, over all points, of the squared 2-norm orthogonal distance between each point and the corresponding hyperplane. We propose an efficient metaheuristic based on a simple criterion for identifying points which are likely to be ill-assigned in the current solution and on their explicit reassignment to other hyperplanes. In the algorithm, an adaptive strategy for updating a control parameter, which determines the number of such points that are actually considered, is combined with two features of Tabu Search. Computational results obtained on real-world and challenging randomly generated instances show that a multi-start version of the best available algorithm provides solutions that are worse than the ones found by our metaheuristic by a factor of 33% on average. Neglecting the instances for which both algorithms provide equivalent solutions, since they may be optimal, the difference amounts to 41%.