O problema da máxima interseção de k-subconjuntos

Autor(es)

Eduardo Theodoro Bogue

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2014-03-27

Membros da banca

Cid Carvalho de Souza; Yuri Abitbol de Menezes Frota; Fábio Luiz Usberti

• Orientador: Cid Carvalho de Souza; Eduardo Candido Xavier

Resumo

Neste projeto, nós estudamos o Problema da Máxima Interseção de k-Subconjuntos (kMIS). Dado um inteiro k, um conjunto base U e uma coleção S de subconjuntos de U, o problema kMIS consiste em selecior k subconjuntos distintos S1, S2, ... , Sk em S cujo tamanho da interseção de |S1 ? S2 ? ... ? Sk| seja máxima. Trata-se de um problema NP-difícil e difícil de ser aproximado que ocorre em aplicações de áreas como biologia computacional e privacidade de dados. Até o nosso conhecimento, nenhum método exato foi proposto para resolver este problema. Neste trabalho, introduzimos cinco formulações de programação linear inteira para o problema, sendo três baseadas no método de Branch-and-Bound e duas no método de Branch-and-Cut. Além disso, uma heurística gulosa e uma meta-heurística GRASP foram desenvolvidas com o intuito de gerar bons limitantes inferiores. A heurística GRASP desenvolvida foi capaz de encontrar soluções muito próximas da solução ótima. Ademais, introduzimos um método muito eficiente de pré-processamento para reduzir o tamanho da entrada. Experimentos computacionais foram realizados de forma a analisar o desempenho dos modelos de programação linear inteira em questão, demonstrando que os modelos baseados no método de Branch-and-Cut obtiveram melhores resultados (AU)

• Processo FAPESP: 12/08298-6 - O problema da Máxima Interseção de k-Subconjuntos
• Beneficiário: Eduardo Theodoro Bogue
• Modalidade de apoio: Bolsas no Brasil - Mestrado