| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000313057 |
| ISSN: | 0101-7438 |
| Authors: | Rangel, Maria Cristina1 Abreu, Nair Maria Maia de2 |
| Institutions: | 1Universidade Federal do Espirito Santo, Departamento de Informatica, Vitoria, Espirito Santo. Brasil 2Universidade Federal do Rio de Janeiro, Instituto Alberto Luiz Coimbra de Pos-Graduacao e Pesquisa de Engenharia, Rio de Janeiro. Brasil |
| Year: | 2003 |
| Season: | May-Ago |
| Volumen: | 23 |
| Number: | 2 |
| Pages: | 265-284 |
| Country: | Brasil |
| Language: | Portugués |
| Document type: | Artículo |
| Approach: | Experimental |
| English abstract | We present an approach to Quadratic Assignment Problem, QAP, via a linear relaxation, through the use of the Linear Assignment Problem, LAP. We define one ordering an LAP-solution-set that makes us compare QAP costs. From here, this poset, partial ordering set, considers coordinates of instances as free variables. We have managed to build a capable algorithm to determine freely comparable permutation pairs. A theorem shows that the order mentioned above is compatible to the one that involves inversion numbers of permutations. We can apply linear and quadratic solutions to permutations and empiric tests are presented to show that the inversion numbers can be used to measure the quality of QAP-solutions. This work is an extension of the article [RA01] published in electronic proceedings of SBPO XXXIII in CD-ROM, 1277-1287, Sobrapo, ILTC, 2001 |
| Portuguese abstract | O Problema Quadrático de Alocação, PQA, pode ser abordado através de uma relaxação na forma do Problema de Alocação Linear, PAL. Introduzimos um poset (conjunto parcialmente ordenado) no conjunto das soluções lineares que nos permite comparar também os custos das soluções do problema quadrático, sem o conhecimento prévio das matrizes que definem seus exemplares. Construímos um algoritmo polinomial capaz de determinar pares de permutações livremente comparáveis, conceito apresentado neste trabalho. Provamos um teorema que garante que os custos associados a tais permutações preservam a ordem dada pelo número de inversões das mesmas. Associando soluções do problema a permutações, testes empíricos são apresentados, visando a validação do número de inversões como um parâmetro de referência para a qualidade das soluções. Este trabalho é uma extensão do artigo [RA01] publicado nos anais do XXXIII SBPO, em CD-ROM, 1277-1287, Sobrapo, ILTC, 2001 |
| Disciplines: | Matemáticas |
| Keyword: | Matemáticas aplicadas, Ordenación parcial, Problema cuadrático de asignación, Problema de asignación lineal, Algoritmos polinomiales |
| Keyword: | Mathematics, Applied mathematics, Partial ordination, Quadratic assignment problem, Linear assignment problem, Polynomial algorithms |
| Full text: | Texto completo (Ver HTML) |
