An Exact Algorithm for the General Quadratic Assignment Problem

The authors develop an algorithm that is based on the linearizaition and decomposition of a general Quadratic Assignment Problem of size n into n2 Linear Assignment problems of size (n-1). The solutions to these subproblems are used to calculate a lower bound for the original problem, and this bound is then used in an exact branch and bound procedure. These subproblems are similar to the'minors'defined by Lawler, but allow calculation of tighter bounds. Computational experience is given for solution to optimization of problems of size up to n = 1