Tight QAP bounds via linear programming

Lower bounds for the quadratic assignment problem (QAP) tend to deterio-rate rapidly with the size of the QAP. Recently, Resende, Ramakrishnan, and Drezner (1995) computed a linear programming based lower bound for the QAP using an interior point algorithm for linear programming to solve the lin-ear programming relaxation of a classical integer programming forn~ulation of the QAP. That linear progralil can be viewed as a two-body interaction for-mulation. Those bounds were found to be the tightest for a large number of instances from QAPLIB, a library of QAP test problems. In this paper, we apply the same interior point approach to compute lower bounds derived from the three-body interaction formulation of Ramachandran and Pekny (1996). All instances from QAPLIB, having dimension up to n = 12, were solved. The new approach produces tight lower hounds (lower bounds equal to the optimal solution) for all instances tested. Attempts to solve the linear programming relaxations with CPLEX (primal simplex, dual simplex, and barrier interio