An exact algorithm for the general quadratic assignment problem (Q1067975)

We develop an algorithm that is based on the linearization and decomposition of a general quadratic assignment problem of size n into \(n^ 2\) 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 permit us to calculate tighter bounds. Computational experience is given for solution to optimality of general quadratic assignment problems of sizes up to \(n=10\).