Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/58964
Title in Portuguese: Abordagens Heurísticas e Exatas para o Problema da Máxima Interseção de k-Subconjuntos
Author: Costa, José Robertty de Freitas
Advisor(s): Dias, Fábio Carlos Sousa
Co-advisor(s): Tavares, Wladimir Araújo
Keywords: Otimização Combinatória
Heurística
Branch and Bound
Programação Linear Inteira
Issue Date: 2020
Citation: COSTA, José Robertty de Freitas. Abordagens Heurísticas e Exatas para o Problema da Máxima Interseção de k-Subconjuntos. 2020. 64 f. Trabalho de Conclusão de Curso (Graduação em Engenharia de Computação)- Universidade Federal do Ceará, Campus de Quixadá, Quixadá, 2020.
Abstract in Portuguese: O Problema da Máxima Interseção de k-Subconjuntos pode ser definido como: dados dois conjuntos L e R, onde L = {S1,S2,··· ,Sp} é uma coleção de p subconjuntos de R = {e1, e2,··· , eq}, e um número inteiro positivo k, temos que encontrar k subconjuntos pertencentes a L, tal que a interseção deles seja máxima. Este problema já foi demonstrado pertencer à classe N P-difícil e possui aplicações na área de privacidade de dados e redes sociais. O objetivo deste trabalho foi propor novas abordagens, exatas e heurísticas, para o Problema da Máxima Interseção de k-Subconjuntos. Neste trabalho, foram propostas duas heurísticas gulosas, dois algoritmos Meta-heuríticos, um algoritmo Branch and Bound e uma formulação de Programação Linear Inteira. Além disso, foi proposto um novo procedimento de Teste de Redução, que visa diminuir a dimensão do problema. Foram geradas instâncias aleatórias e realizados diversos testes computacionais. Os resultados computacionais evidenciaram que os algoritmos Meta-heurísticos propostos superam o algoritmo heurístico de estado da arte em qualidade de solução ou em tempo de execução. Em relação às abordagens exatas, o algoritmo Branch and Bound proposto se mostrou mais eficiente que o método do estado da arte em instâncias onde o grafo possui uma densidade baixa ou média.
Abstract: The Maximum k-Subset Intersection Problem can be defined as follows: given two sets L and R, where L = {S1,S2,··· ,Sp} is a collection of p subsets of R = {e1, e2,··· , eq}, and a positive integer k, we have to find k subsets belonging to L such that their intersection is maximum. This problem has already been shown to belong to the class N P-hard and has applications in the area of data privacy and social networks. The objective of this work was to propose new approaches, exact and heuristic, for the Maximum k-Subset Intersection Problem. In this work, we propose two greedy heuristics, two Metaheuristics algorithms, a Branch and Bound algorithm and a formulation of Integer Linear Programming. In addition, a new Reduction Test procedure has been proposed, which aims to reduce the scale of the problem. Random instances were generated and several computational tests were performed. The computational results showed that the proposed Metaheuristic algorithms surpass the state-of-the-art heuristic algorithm in solution quality or in execution time. Regarding the exact approaches, the proposed Branch and Bound algorithm proved to be more efficient than the state-of-the-art method for instances where the graph has a low or medium density.
URI: http://www.repositorio.ufc.br/handle/riufc/58964
metadata.dc.type: TCC
Appears in Collections:ENGENHARIA DE COMPUTAÇÃO-QUIXADÁ - Monografias

Files in This Item:
File Description SizeFormat 
2020_tcc_jrdefcosta.pdf607,87 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.