Um algoritmo exato para o problema da diversidade máxima

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

23/08/2011

RESUMO

O termo diversidade está relacionado à variedade de características, idéias ou elementos diferentes entre si dentro de um determinado contexto, sendo importante para o pluralismo, heterogeneidade, tolerância mútua e sobrevivência de idéias. Existem diversos tipos de diversidade em diferentes áreas do conhecimento humano. Entre eles, podemos citar a diversidade religiosa, social, linguística, sexual, cultural e biológica. Na área de otimização combinatória, o Problema da Diversidade Máxima (PDM) consiste em selecionar um subconjunto de m elementos de um conjunto de n elementos, de tal forma que a diversidade entre os seus elementos selecionados seja máxima. Neste trabalho é apresentado uma nova formulação para este problema baseado na Técnica de Reformulação de Linearização. Devido às características da formulação proposta e da dificuldade de resolução, o método de Decomposição de Benders Revisado é aplicado ao problema, assim como uma técnica de pré-processamento de modo a acelerar a sua convergência. Testes são realizados para avaliar o desempenho do método aplicado ao problema e em seguida, uma análise é feita comparando-o com outro algoritmo descrito na literatura. Os resultados computacionais mostram que o método proposto demonstra ser competitivo frente aos métodos exatos descritos na literatura

ASSUNTO(S)

engenharia de produção teses. método de decomposição teses.

ACESSO AO ARTIGO

Documentos Relacionados