K.G. Ramakrishnan, M.G.C. Resende, and P.M. Pardalos

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: