Optimization and Systems Theory Seminar
Friday, August 15, 1997, 11.00-12.00, Room 3721, Lindstedtsvägen 25


Professor Panos M. Pardalos
Center for Applied Optimization, ISE Department
University of Florida
Gainesville, FL 32611-6595, USA
E-mail: pardalos@ise.ufl.edu

Recent approaches for solving quadratic assignment problems

In this talk we discuss several new developments regarding the quadratic assignment problem [1,2,3,4]. In particular, we discuss 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. 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. Extensions to the implementation are discussed.

[1] P. M. Pardalos and H. Wolkowicz, Quadratic Assignment and Related Problems, DIMACS Series Vol. 16, American Mathematical Society (1994).
[2] P. M. Pardalos, M. G. C. Resende and Y. Li, FORTRAN Subroutines for Approximate Solution of Dense Quadratic Assignment Problems Using GRASP, ACM Transactions on Mathematical Software Vol. 22, No. 1 (1996), pp. 104-118.
[3] P. M. Pardalos, K. G. Ramakrishnan, M. G. C. Resende and Y. Li, Implementation of a Variance Reduction Based Lower Bound in a Branch and Bound Algorithm for the Quadratic Assignment Problem, SIAM J. Optim. Vol. 7 No. 1, (1997), pp. 280-294.
[4] P. M. Pardalos, K. G. Ramakrishnan, and M. G. C. Resende, A Branch and Bound for the Quadratic Assignment Problem Using a Lower Bound based on Linear programming, In State of the Art in Global Optimization, (edit. C. Floudas and P.M. Pardalos), Kluwer Academic Publishers (1996), pp. 57-73.

Calendar of seminars
Last update: August 5, 1997 by Anders Forsgren, andersf@math.kth.se.