Uma heurística langrangeana para o problema de ponderação de rodadas

Detalhes bibliográficos
Ano de defesa: 2014
Autor(a) principal: Araújo, Paulo Henrique Macêdo de
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/10587
Resumo: In this dissertation, our main objective was to develop a technique for resolution to a problem in the area of telecommunications. The problem in question is called Round Weighting Problem (RWP) and was originally proposed in (KLASING; MORALES; P eRENNES, 2008). The context of the problem involves a wireless network where communications are performed by radio waves and the network operates through a network operation that satis es the constraints of the problem. Initially, we explain how a radio network is formed and describe the mode of operation of the radio network with restrictions using a mathematical model. Then, we formalize the RWP as an optimization problem, specifying their restrictions, corresponding to the generation of the set of possible network operations, and optimization criterion, regarding the use of network resources. Subsequently, we show a preliminary study of the Fractional Coloring problem (FC problem) and present a technique to solve this problem through the use of a lagrangian heuristic based on a lagrangian relaxation of an integer programming formulation of the problem. This resolution technique is then adapted to the RWP, consisting in the main contribution of our research. Finally, we show the computational results and analyzes of our implementations for the Fractional Coloring problem and RWP.