A Branch and Bound Algorithm for the Quadratic Assignment Problem using a Lower Bound Based on Linear Programming

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


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 Page
Last modified: 28 June 2002

Copyright Notice