Métodos exatos e aproximativos para o problema de agrupamento capacitado com centro geométrico

• Ano de defesa: 2020
• Autor(a) principal: Batista, Pablo Luis Fernandes
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual do Ceará
• Palavras-chave em Português: Centro geométrico - Problema de agrupamento capacitado; Ciência da computação; Metodo Branch
• Link de acesso: https://siduece.uece.br/siduece/trabalhoAcademicoPublico.jsf?id=97151

Este trabalho apresenta métodos exatos e aproximativos para resolver o Problema de Agrupamento Capacitado com Centro Geométrico (PACCG). O PACCG consiste em definir conjuntos de indivíduos com capacidade limitada e máxima similaridade interna entre indivíduos do mesmo conjunto. Cada conjunto é composto por indivíduos dos quais se agrupam em torno do centro geométrico, e é isso que determina a medida de similaridade entre os conjuntos. O PACCG é um problema da classe NP-hard, portanto um problema difícil de ser resolvido com exatidão. Abordagens Branch-and-Bound com e sem limitações para geração de colunas foram estudadas e avaliadas sobre instâncias conhecidas na literatura. Um método Branch-and-Bound requer bons limites superiores e inferiores. Para obter os limites superiores estudou-se uma meta-heurística Busca Tabu que obteve boas soluções para as instâncias aqui trabalhadas. Para obter os limites inferiores estudou-se uma Relaxação Lagrangeana sobre o modelo matemático original proposto para o problema. Durante a obtenção destes limites, dados e informações importantes foram revelados. A partir da busca por limites inferiores, estudos relacionados ao modelo matemático do PACCG foram feitos e algumas questões importantes sobre os solvers disponíveis no mercado foram levantadas. Também, a partir da busca por limites superiores, estudos de métodos alternativos ajudaram a cogitar e desenvolver um novo framework apoiado por um método exato ou aproximativo relacionado ao Problema Generalizado de Atribuição que contribuiu para que uma nova variação do PACCG fosse aqui introduzida. Surgiu então, o Problema de Agrupamento Capacitado Heterogêneo com Centro Geométrico (PACHCG), onde nele existe a possibilidade de se formar grupos com capacidades distintas.