Relaxação lagrangeana com divisão em clusters aplicada ao problema da diversidade máxima / Lagrangean relaxation with clustering division applied to the maximum diversity problem

AUTOR(ES)

Carlos Renato Seabra Almeida Junior

DATA DE PUBLICAÇÃO

2009

RESUMO

O Problema da Diversidade Máxima é um problema de natureza combinatória com o objetivo de selecionar os m itens mais distintos de um conjunto N = {e$ _1$ , e$ _2$ , ..., e$ _n$ }, com emph{n} elementos, tal que emph{m < n} e existe uma medida de diversidade para cada par de elementos. A literatura apresenta a formulação quadrática do problema e sua linearização. A proposta deste trabalho consiste no cálculo de limitantes superiores com base nessa formulação linearizada. A partir da confecção de um grafo modelado para representar o Problema da Diversidade Máxima, esse grafo é particionado em emph{k} clusters e o problema, dividido em emph{k} subproblemas relacionados aos clusters criados. Esses subproblemas são formulados de acordo com a metodologia utilizada. Nesse processo de divisão, algumas restrições são relaxadas no sentido lagrangeano e a solução final apresenta um limitante superior para o problema. Duas técnicas distintas foram utilizadas separadamente neste trabalho, a fim de melhorar esse limitante em processos iterativos: o método dos subgradientes e o da geração de colunas. Embora os esforços tenham sido estritamente direcionados à formulação e à modelagem matemática do problema principal e seus subproblemas, ambos os métodos foram implementados e executados para fim de análise e comparação de resultados.

ASSUNTO(S)

problema da diversidade máxima geração de colunas relaxação lagrangeana método dos subgradientes particionamento de grafo otimização combinatória programação linear maximun diversity problem column generation lagrangean relaxation sub gradients method graph partitioning combinatorial optimizatiom linear programming

Documentos Relacionados

• Relaxação lagrangeana com divisão em clusters aplicada ao problema da diversidade máxima
• Relaxação langrangena com divisão em clusters para alguns problemas de otimização modelados em grafos de conflitos
• Relaxação langrangena com divisão em clusters para alguns problemas de otimização modelados em grafos de conflitos
• Relaxação lagrangeana com fixação de variáveis aplicada ao problema de sequenciamento em uma máquina
• Aplicação da relaxação lagrangeana e do algoritmo genético construtivo na solução do problema probabilístico de localização-alocação de máxima cobertura