A carregar...
Publicação
Analysis of Formulations for the Cluster Partitioning Problem
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 3.66 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
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.
Descrição
Tese de mestrado, Estatística e Investigação Operacional (Investigação Operacional), 2022, Universidade de Lisboa, Faculdade de Ciências
Palavras-chave
k-plex grafo partição relaxações de cliques Teses de mestrado - 2023