A constructive algorithm based on an algebraic approach of the allocation quadratic problem

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. In this theorem, the QAP solution cost is associated to the number of inversions of the linear correspondent. Although recognizing if a linear solution corresponds 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 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.