Analysis of Formulations for the Cluster Partitioning Problem

Abstract

A graph is an abstract structure that is frequently used to model interpersonal relationships and/or social interactions. Since relationships between individuals are frequently represented by graphs, it makes sense to utilise graphs to look for groups of those individuals. These clusters are best modelled as cliques, however when it is necessary to represent the underlying issues when the amount of cohesion required is less than the level imposed by a clique, relaxed versions of those clusters may be taken into consideration. The k-plex relaxation is the one being examined in this project. Most of the formulations proposed in the literature aim to solve the Maximum Clique Problem or the Graph Partitioning Problem. The Cluster Partitioning Problem is known as the problem of partitioning a graph’s nodes into distinct clusters. This problem can be viewed as a specific case of the general Graph Partitioning Problem, where each set within the partition must respect certain requirements depending on the type of cluster being considered. In the present project, three formulations were proposed to solve the Cluster Partitioning Problem when the clusters being considered are k-plexes. These formulations were based on formulations proposed for the Maximum K-plex Problem and for the K-Plex Partitioning Problem taking into consideration different objective functions. Furthermore, improvements and extended formulations were presented for these models. Three sets of instances were considered to evaluate the performance of each model. Computational results show that when comparing the three base formulations, the Coneighbourhood Model presents the best results for the first objective function studied and the Complementary Edge Model and the Cluster Representative Model present the best solutions for the second objective function studied. However, when enhancements and extended formulations are introduced, it can be concluded that for both objective functions the Linearised Extended Cluster Representative Model is the one that produces the overall best results for the instances studied.