Journal: | Pesquisa operacional |
Database: | PERIÓDICA |
System number: | 000313145 |
ISSN: | 0101-7438 |
Authors: | Resendo, Leandro Colombi1 Rangel, Maria Cristina2 |
Institutions: | 1Universidade Federal do Espirito Santo, Departamento de Engenharia Eletrica, Vitoria, Espirito Santo. Brasil 2Universidade Federal do Espirito Santo, Departamento de Informatica, Vitoria, Espirito Santo. Brasil |
Year: | 2006 |
Season: | Ene-Abr |
Volumen: | 26 |
Number: | 1 |
Pages: | 129-144 |
Country: | Brasil |
Language: | Portugués |
Document type: | Artículo |
Approach: | Analítico, descriptivo |
English abstract | The Quadratic Assignment Problem, QAP, was studied using an algebraic approach through a linear relaxation, the Linear Assignment Problem, LAP. The reason for this approach is the Inversion Theorem demonstrated by Rangel [Ran00]. In this theorem, the QAP solution cost is associated to the number of inversions of the linear correspondent. Although recognizing if a linear solution correspond to a QAP solution is polynomial, there are much more LAP solutions than QAP solutions, and therefore to find them is a hard work. We construct a matrix that stores information about LAP solutions that are able to generate QAP solutions. The Inversion Theorem in conjuction with this matrix permitted us to present a constructive method that generates good initial solutions. The great advantage of this matrix is the low computational cost of time and memory. A parallel version of this algorithm is proposed and implemented in this work |
Portuguese abstract | 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 |
Disciplines: | Matemáticas |
Keyword: | Matemáticas aplicadas, Problema cuadrático de asignación, Problema de asignación lineal, Teorema de la inversión, Algoritmos |
Keyword: | Mathematics, Applied mathematics, Quadratic assignment problem, Linear assignment problem, Inversion theorem, Algorithms |
Full text: | Texto completo (Ver HTML) |