### 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.
*