On an integer linear programming for correlation clustering | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 70. DOI: 10.17223/20710410/70/3

Clustering problems form an important section of data analysis. In these problems, we need to partition a given set of objects into several subsets (clusters) based on the similarity of the objects to each other. Correlation clustering is a formalization of the clustering problem. Similar objects are connected by edges of a graph and vertices are in one-to-one correspondence with the objects. The problem has several variants: with limited number and size of clusters, weighted, and directed. All known variants are NP-hard. We investigate an approach to solve the problems that involves building integer linear programming models. We review existing models and propose new approaches to model building. The new models can be used both to find exact solutions and to construct approximate algorithms. An experimental study has been conducted to evaluate the computation time to find exact solutions by algorithms based on different models. It showed that one of the algorithms based on the new models is faster than others in finding solutions for a variant of the problem with a limited number of clusters.