GRASP para o PQA: um limite de aceitação para soluções iniciais

AUTOR(ES)

Range, Maria Cristina, Abreu, Nair Maria Maia de, Boaventura-Netto, Paulo Oswaldo

FONTE

Pesquisa Operacional

DATA DE PUBLICAÇÃO

2000-06

RESUMO

O Problema Quadrático de Alocação (PQA) pertence à classe dos problemas NP-Hard e desafia os pesquisadores tanto em sua teoria quanto em sua parte computacional. Pela sua alta complexidade muitos métodos heurísticos têm sido desenvolvidos para tentar resolvê-lo aproximadamente. A metaheurística GRASP (greedy randomized adaptive search procedures) se mostrou bastante eficiente. Neste trabalho, uma proposta para descartar soluções iniciais supostamente ruins é apresentada com base na normalização de custos calculadas num intervalo entre limites de solução. Para este GRASP restrito, foi observada uma redução do tempo computacional para encontrar as soluções ótimas ou soluções viáveis de boa qualidade quando comparado ao GRASP original.

ASSUNTO(S)

grasp metaheurísticas problema quadrático de alocação

Documentos Relacionados

• Estratégias de paralelização para um algoritmo GRASP multicritério
• Soluções para um sistema de equações elípticas envolvendo o p-Laplaciano
• Proposta e avaliação de heurísticas grasp para o problema da diversidade máxima
• Uma heurística GRASP para o problema de dimensionamento de lotes com múltiplas plantas
• Competências iniciais para o processo de alfabetização