Lower bounds for the quadratic assignment problem via triangle decompositions

The authors consider transformations of the (metric) Quadratic Assignment Problem (QAP) that exploit the metric structure of a given instance. They show in particular how the structural properties of rectangular grids can be used to improve a given lower bound. The present work is motivated by previous research of Palubetskes, and it extends a bounding approach proposed by Chakrapani and Skorin-Kapov. The computational results indicate that the present approach is practical; it has been applied to problems of dimension up to n=150. Moreover, the new approach yields by far the best lower bounds on most of the instances of metric QAPs that the authors considered.