Título: Problema de recobrimento de conjuntos com agrupamento: modelos e algoritmos
Aluno: ARTUR FERREIRA BRUM
Orientador: Felipe Martins Müller
Data: 14/04/15
Horário: 17h15min
Local: Sala de Apoio do prédio 67 UFSM
Banca:
Dr. FELIPE MARTINS MULLER – Orientador
Dr. HAROLDO GAMBINI SANTOS – UFOP
Dr. OLINTO CESAR BASSI DE ARAUJO – UFSM
Drª. VIVIANE CATIA KOHLER – UFSM – Suplente
Resumo: Este trabalho aborda o problema de recobrimento de conjuntos com agrupamento, definido como uma variante do problema de recobrimento de conjuntos clássico, na qual os conjuntos estão dispostos em K agrupamentos disjuntos. São apresentadas duas aplicações práticas para o problema encontradas na literatura. A primeira delas tem origem na engenharia elétrica, especificamente no problema abordado por Fritzen et al. (2012). Uma característica intrínseca ao problema, levou à generalização da atribuição dos conjuntos aos agrupamentos, de forma que a intersecção seja permitida. A segunda aplicação é oriunda da indústria de mineração e devida a Bilal et al. (2014), que propõem um conjunto de instâncias e uma meta-heurística baseada em iterated tabu search (ITS). Duas contribuições deste trabalho se referem à meta-heurística ITS. A primeira consiste em uma abordagem paralela para o componente de busca tabu, enquanto a segunda contribuição reside na adição de uma vizinhança resolvida com programação inteira e que faz uso de hard variable fixing. A ideia subjacente ao uso da vizinhança é ocupar o tempo economizado na paralelização com o polimento de soluções promissoras obtidas pela busca tabu. É apresentada ainda uma terceira contribuição, que consiste em uma formulação matemática com geração de colunas para obtenção de limitantes superiores para as instâncias consideradas. Os resultados computacionais obtidos mostram melhora na qualidade da solução para a ampla maioria das instâncias. Dada a magnitude dos custos envolvidos no problema, é possível concluir que o aprimoramento da meta-heurística ITS com as sugestões deste trabalho pode ser de significativo benefício econômico.
