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.