A comparison of two hybrid methods for constrained clustering problems

作者：de Oliveira Rudinei Martins^*; Chaves Antonio Augusto; Nogueira Lorena Luiz Antonio

来源：Applied Soft Computing, 2017, 54: 256-266.

DOI：10.1016/j.asoc.2017.01.023

• Column generation
• BRKGA
• Clustering

This paper proposes two hybrid heuristics to solve the constrained clustering problem. This problem consists of partitioning a set of objects into clusters with similar members that satisfy must-link and cannot-link constraints. A must-link constraint indicates that two selected objects must be in the same cluster, and cannot-link constraint means that two selected objects must be in distinct clusters. The two proposed hybrid methods are biased random key genetic algorithm (BRKGA) with local search (LS) heuristic and column generation (CG) with path-relinking (PR) and local search (LS) heuristic. Computational experiments considering instances available in the literature are presented to demonstrate the efficacy of the proposed methods to solve the constrained clustering problem. Moreover, the results of the CG and BRKGA are compared with the CCCG, CP and CPRBBA method.

• 出版日期2017-5