Um algoritmo construtivo baseado em uma abordagem algébrica do problema quadrático de alocação

Pesquisa Operacional

Leandro Colombi Resendo²  Maria Cristina Rangel¹ 

[1] ,CT Universidade Federal do Espírito Santo Departamento de Engenharia Elétrica Vitória ES

关键词: problema quadrático de alocação;    problema de alocação linear;    teorema das inversões;    quadratic assignment problem;    linear assignment problem;    inversion theorem;   

DOI  :  10.1590/S0101-74382006000100007

来源: SciELO

【 摘 要 】

O Problema Quadrático de Alocação, PQA, foi estudado utilizando uma abordagem algébrica através de uma relaxação linear, o Problema de Alocação Linear, PAL. A utilização dessa abordagem se deve ao fato de existir na literatura o Teorema das Inversões demonstrado por Rangel em [Ran00] que associa o custo de uma solução do PQA ao número de inversões de sua correspondente linear no PAL. Embora seja polinomial o reconhecimento de uma solução linear viável para o PQA, caracterizar no conjunto de todas as soluções do PAL quais são as que satisfazem o PQA é uma tarefa extremamente difícil. Neste trabalho construímos uma matriz que armazena informações de soluções lineares capazes de gerar soluções quadráticas. Combinando esse mapeamento com o Teorema das Inversões apresentamos um método construtivo que gera soluções iniciais de boa qualidade. A grande vantagem dessa matriz é que seu custo computacional e gasto de memória são baixos. Propomos também uma versão paralela deste algoritmo.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License