Novas formulações e técnicas de pré-processamento para o problema de particionamento de grafo em cliques

• Ano de defesa: 2019
• Autor(a) principal: Lorena, Luiz Henrique Nogueira [UNIFESP]
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de São Paulo (UNIFESP)
• Palavras-chave em Português: Graph Clustering; Integer Linear Programming; Preprocessing Techniques; Agrupamento De Dados Em Grafo; Programação Linear Inteira; Técnicas De Pré-Processamento.
• Link de acesso: https://sucupira.capes.gov.br/sucupira/public/consultas/coleta/trabalhoConclusao/viewTrabalhoConclusao.jsf?popup=true&id_trabalho=7716857; https://repositorio.unifesp.br/handle/11600/59482

Graph clustering is a fundamental technique in data analysis, used to understand the relation between the entities of a dataset. In this wor k, we have studied a graph clustering problem called Clique Partitioning Problem. In this problem, the objective is to partition the vertices of a weighted complete graph, such that the value of the sum of the edge’s weight within the obtained groups is maximum. The authors who suggested this problem proposed a linear integer programming formulation to solve it. This formulation, however, creates mathematical models with a high number of variables and constraints, which require a high computational effort, in terms of time and memory, to be solved. The authors, however, have empirically demonstrated that a large number of constraints inserted in mathematical models are redundant and can be disregarded. Despite this, the authors did not identified the reason for such behavior. Recent studies tr y to identify the redundancy of this formulation and prevent it to be inserted into the mathematical model. Such models require less computational effort to be solved. Another approach used in the literature, to attenuate the issue of the original formulation, is to reduce the size of the graph instance that represents the problem through a preprocessing technique. A smaller graph gives rise to a mathematical model with fewer variables and constraints. This thesis followed the concepts presented in these works to propose new formulations and preprocessing techniques. The computational experiments show that the techniques proposed in this work create mathematical models that are more compact, and which require less computational effort to be solved than the models created from the formulations proposed in the literature.