Tight QAP bounds via linear programming

K.G. Ramakrishnan, M.G.C. Resende, B. Ramachandran, and J.F. Pekny

In Combinatorial and Global Optimization, P.M.Pardalos, A. Migdalas, and  R. Burkard, eds., World Scientific Publishing Co., Singapore, pp. 297-303, 2002


Lower bounds for the quadratic assignment problem (QAP) tend to deteriorate 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 linear programming relaxation of a classical integer programming formulation of the QAP. That linear program can be viewed as a two body interaction formulation.  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 bounds (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 interior point method) were successful only for the smallest instances (N < 7 for the barrier method, N < 8 for the primal simplex method, and N < 9 for the dual simplex method).

PDF file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 19 August 2005

Copyright Notice