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
ABSTRACT
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 PageLast modified: 19 August 2005