A Heuristic Approach to Quadratic Assignment Problem

A new algorithm for solving quadratic assignment problems is presented. The algorithm, which employs a sequential search technique, constructs a matrix of lower bounds on the costs of locating facilities at different sites. It then improves the elements of this matrix, one by one, by solving a succession of linear assignment problems. After all the elements of the matrix are improved, a feasible assignment is obtained, which results in an improved value for the objective function of the quadratic assignment problem. The procedure is repeated until the desired accuracy in the objective function value is obtained.