Made available in DSpace on 2019-04-05T23:04:27Z (GMT). No. of bitstreams: 0
Previous issue date: 2005-12-28 / This work presents a comparative study of Lagrangean relaxation using Subgradient and Spaces Dilatation methods to solve the generalized assignment problem in diversity and capacity constraints (GAP-DC). This problem,appears during the planning of a mobile telephone network. It consists in assigning radio base stations to hubs at a minimal cost, so that the demands
on each station and on the capacity of each hub can be met. The GAP-DC is known to be NP-hard. Some computational tests was made with instances acquired from a instances generator and computational results indicatethat although Subgradient algorithms are capable of producing good lower bounds, but the tests based on Spaces Dilatation methods prove that this algorithm get better lower bounds, in a better computational time as well as in the first iteration. / Este trabalho apresenta um estudo comparativo entre a relaxacao Lagrangeana associada aos métodos de Subgradiente e de Dilatação de Espaços aplicada na resolução do Problema de Alocação Generalizada com Restrições de Diversidade e Capacidade (PAG-DC). Este problema surge durante o projeto de uma rede de telefonia celular e consiste na atribuição de estações rádio base a hubs, a um custo mínimo, tal que as demandas de cada estação e a capacidade de cada hub sejam atendidas. O PAG-DC é conhecido ser NP-difícil. Foram realizados alguns experimentos computacionais com instâncias geradas a partir de um gerador de instâncias e os resultados obtidos indicam
que os algoritmos baseados no método de Subgradiente são capazes de encontrar bons limitantes inferiores, porém os testes baseados no método de Dilatação de Espaços obtiveram melhores limitantes em um tempo computacional menor e em uma única iteração.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.unifor.br:tede/70000 |
| Date | 28 December 2005 |
| Creators | Rigolon, Adriana Aparecida |
| Contributors | Pinheiro, Plácido Rogério, Macambira, Elder Magalhaes, Pinheiro, Plácido Rogério, Macambira, Elder Magalhaes, Silva, Jose Lassance de Castro |
| Publisher | Universidade de Fortaleza, Mestrado Em Informática Aplicada, UNIFOR, Brasil, Centro de Ciências Tecnológicas |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UNIFOR, instname:Universidade de Fortaleza, instacron:UNIFOR |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 5443571202788449035, 500, 500, -7645770940771915222 |
Page generated in 0.0016 seconds