Um algoritmo exato para o problema das P-medianas

Detalhes bibliográficos
Ano de defesa: 1989
Autor(a) principal: Hilcéa Ferreira Marengoni
Orientador(a): Luiz Antonio Nogueira Lorena, Edson Luiz França Senne
Banca de defesa: Edgard Dias Batista Júnior
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Instituto Nacional de Pesquisas Espaciais (INPE)
Programa de Pós-Graduação: Programa de Pós-Graduação do INPE em Análise de Sistemas e Aplicações
Departamento: Não Informado pela instituição
País: BR
Resumo em Inglês: This work reports a study of a few heuristic and exact methods for solving the p-median problem. It particularly covers an exact algorithm based on an integer programming formulation of the problem. A "branch and bound" algorithm is presented and the bounds are obtained by solving the lagrangean relaxation and using the subgradient optimization method. A data structure that takes into account the matricial character of the problem is developed and the algorithm is implemented to run on a IBM-PC micro-computer.
Link de acesso: http://urlib.net/sid.inpe.br/iris@1905/2005/07.27.06.49
Resumo: Este trabalho descreve o estudo de alguns métodos exatos e heurísticos para resolver o problema da p-medianas. Em particular enfoca um algoritmo exato baseado em uma formulação de programação inteira do problema. Um algoritmo do tipo "branch and bound" é utilizado e os limitantes são obtidos através da relaxação lagrangeana do problema usando um método de otimização por subgradientes. Uma estrutura de dados explorando a estrutura matricial do problema é desenvolvida e a implementação é feita em microcomputadores IBM-PC.