Tuesday,
October 21, 12:00 p.m. ECG 317
Hans Mittelmann
Dept. Math. & Stats
Lower Bounds for the Quadratic Assignment Problem
via Semidefinite Relaxations
Abstract
The quadratic assignment problem (QAP) is recognized as one of the
hardest combinatorial optimization problems. It also models
various application problems such as facility location in
operations research, problems in chip design, image processing,
and communication. The unknown is a permutation matrix of order
N and heuristic methods generating permutations and trying to
improve them yield upper bounds on the optimum. The difficulty
consists in finding efficient methods to obtain lower bounds.
One relaxes the binary variables to continous variables and so
far methods proposed need up to N^4 variables and/or constraints.
We propose a relaxation to a so-called semidefinite program
of order N^2. We show that this approach yields strong lower
bounds and can be used for sizes well over 200. It improves
the best known bounds considerably for several of the larger
cases. Initial results indicate that it is
possible to incorporate it into a branch&bound
framework in order to solve QAPs of medium size exactly.
For further information please contact:
mittelmann@asu.edu