Orientador: Marcus Vinicius S. Poggi de Aragão

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

Resumo: Esta dissertação tem como tema central o Problema de Recobrimento de um Conjunto (SCP - Set Covering Problem). O objetivo principal é a proposta de uma nova abordagem para sua resolução, mais precisamente, este objetivo visa o desenvolvimento de um método heurístico, multi-algorítmico,...

Resumo: Esta dissertação tem como tema central o Problema de Recobrimento de um Conjunto (SCP - Set Covering Problem). O objetivo principal é a proposta de uma nova abordagem para sua resolução, mais precisamente, este objetivo visa o desenvolvimento de um método heurístico, multi-algorítmico, baseado no paradigma de Times Assíncronos. Um segundo objetivo desta dissertação, e de grande importância na funda­mentação do método ora proposto, é um estudo das principais características estruturais do problema; de sua formulação como um problema de programação linear inteira 0-1 e dos principais métodos computacionais (heurísticos e exatos) atualmente disponíveis para sua resolução. Times Assíncronos são organizações de software que visam a interação efici­ente entre vários algoritmos, para a resolução de problemas adequados à aborda­gem multi-algorítmica. A arquitetura proposta utiliza métodos aproximados para a resolução do SCP e do dual da relaxação linear do mesmo. Esta abordagem primal-dual permite garantir que a melhor solução encontrada esteja a um certo percentual da solução ótima, ou mesmo, eventualmente, provar a otimalidade da solução. Segundo este enfoque, os principais componentes da arquitetura proposta são algoritmos gulosos e de consenso, procedimentos de busca tabu, métodos de otimização por subgradientes e geradores de planos de corte. Os principais métodos exatos para a resolução do SCP são baseados em metodologias enumerativas. A maioria desses métodos combina ao esquema de enumeração diversas das técnicas heurísticas utilizadas na arquitetura aqui proposta. Contudo, esses métodos apresentam desempenho insatisfatório para algu­mas classes de instâncias, por não obterem boas soluções em um limite razoável de tempo. A arquitetura proposta foi aplicada a instâncias dessas classes de difícil reso­lução. Os resultados obtidos mostraram que é possível alcançar, com um esforço computacional aceitável, resultados no mínimo comparáveis aos dos melhores algoritmos para o SCP

Abstract: The development of an Asynchronous Team Method for heuristic resolution of the Set Covering Problem (SCP) is the main focus of this dissertation. Asynch­ronous Teams are software organizations that aim to efficient interaction among several algorithms for the resolution of problems that...

Abstract: The development of an Asynchronous Team Method for heuristic resolution of the Set Covering Problem (SCP) is the main focus of this dissertation. Asynch­ronous Teams are software organizations that aim to efficient interaction among several algorithms for the resolution of problems that fit in a multi-algorithm approach. Another goal of this work is an extensive study of the SCP which covers: the SCP structures its formulation as a 0-1 ILP; and the description of the main heuristic and exact methods currently available for its resolution. This study is most1y required since we are concerned with the development of a multi-algorithm method. The resulting software architecture makes use of approximate algorithms for the resolution of the se P and its continuous relaxation dual. This primal-dual approach guarantees the best found solution to be at a certain percentage of the optimal solution and, eventually, proves the solution optimality. The main components of the proposed architecture are greedy and consensus algorithms, tabu search procedures, subgradient methods and cutting plane generators. The main exact methods for the se P resolution are based on enumerative methodologies. Most of these methods deploys many of the heuristic technics used in the proposed architecture to the enumeration scheme. However, these methods have a poor performance in some instance classes, because they do not obtain good solutions in a reasonable time limit. The proposed architecture was applied to particularly hard instances. The obtained results show that it is possible to reach solutions, at an acceptable computational effort, that are at least comparable to the ones obtained by the best algorithms for the SCP