| Revista: | Pesquisa operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000313145 |
| ISSN: | 0101-7438 |
| Autores: | Resendo, Leandro Colombi1 Rangel, Maria Cristina2 |
| Instituciones: | 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 |
| Año: | 2006 |
| Periodo: | Ene-Abr |
| Volumen: | 26 |
| Número: | 1 |
| Paginación: | 129-144 |
| País: | Brasil |
| Idioma: | Portugués |
| Tipo de documento: | Artículo |
| Enfoque: | Analítico, descriptivo |
| Resumen en inglés | 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 |
| Resumen en portugués | 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 |
| Disciplinas: | Matemáticas |
| Palabras clave: | 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 |
| Texto completo: | Texto completo (Ver HTML) |
