Abstract: In correlation clustering (cluster editing) we must split vertices of a graph into clusters based on their similarity, which is given by the edge structure of the graph. There are different formulations of the problem: with a constraint on the number of clusters, their cardinality, etc. The problems under consideration are NP-hard. Thus weneedtobuild exact algorithms and mathematical programming models. We consider a problem in which the number of clusters does not exceed a predefined constant. New integer linear programming models are constructed for this problem. We also provide an analysis of the experimental study, which aims to compare new models with known models.

Cite: Morshinin A.
New integer linear programming models for a variant of correlation clustering problem
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 Jun - 6 Jul 2024