In State of the Art in Global Optimization: Computational Methods and Applications, C. Floudas and P.M. Pardalos, eds., Kluwer Academic Publishers, pp. 57-73, 1996
ABSTRACT
In this paper, we study a branch and bound algorithm
for the quadratic assignment problem (QAP) that uses a lower bound based
on the linear programming (LP) relaxation of a classical integer
programming formulation of the QAP. Computational experience with the
branch and bound algorithm on several QAP test problems is
reported. The linear programming relaxations are solved with an
implementation of an interior point algorithm that uses a preconditioned
conjugate gradient algorithm to compute directions. The branch and
bound algorithm is compared with a similar branch and bound algorithm
that uses the Gilmore-Lawler lower bound (GLB) instead of the LP-based
bound. The LP-based algorithm examines a small portion of the
nodes explored by the GLB-based algorithm.
PostScript file of full paper
Go back
Mauricio G.C. Resende's Home PageLast modified: 28 June 2002