Hybrid heuristics based on column generation with path-relinking for clustering problems

•The paper examines hybrid heuristics for solving clustering problems.•Methods are based on the application of a column generation technique for solving p-median problems.•Five heuristics are tested with CRand indexes.•Computational results are compared with recent methods in literature.

This paper examines hybrid heuristics for solving clustering problems. The clustering problem can be defined as the process of separating a set of objects into groups such that members of a group are similar to each other. The methods are based on the application of a column generation technique for solving p-medians problems. Five heuristics are derived directly from the column generation algorithm: a solution made feasible from the master problem, the column generation solution, a heuristic with path-relinking considering the initial columns of the column generation procedure, a solution of the master problem with path-relinking and the column generation process with path-relinking. Solutions are tested with the external measure CRand and the computational results compared to recent methods in literature.