Orientador: Marcus Vinicius S. Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-21T10:33:41Z (GMT). No. of bitstreams: 1
Longo_HumbertoJose_M.pdf: 2296998 bytes, checksum: cb6cef9a3b19187ee26dc91e8fe15b17 (MD5)
Previous issue date: 1995 / 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 fundamentaçã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 eficiente entre vários algoritmos, para a resolução de problemas adequados à abordagem 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 algumas 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 resoluçã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. Asynchronous 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 / Mestrado / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/276125 |
| Date | 26 October 1995 |
| Creators | Longo, Humberto Jose |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Aragão, Marcus Vinicius Soledade Poggi de, 1959- |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Computação Científica, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 75f., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds