Article,
Um algoritmo construtivo baseado em uma abordagem alg�brica do problema quadr�tico de aloca��o
Pesquisa Operacional, 26 (1): 129-144 (2006)
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.
