Ranking scalar products to improve bounds for the quadratic assignment problem (Q1058988)

The eigenvalue bound for the quadratic assignment problem (QAP) is successively improved by considering a set of k-best scalar products, related to the QAP. An efficient procedure is proposed to find such a set of k-best scalar products. A class of QAPs is described for which this procedure in general improves existing lower bounds and at the same time generates good suboptimal solutions. The method leaves the user with a large flexibility in controlling the quality of the bound. However, since the method is sensitive to input data it should only be used in combination with other bounding rules.