MASSACHUSETTS INSTITUTE OF TECHNOLOGY
OPERATIONS RESEARCH CENTER
FALL 2004 SEMINAR SERIES

DATE

Thursday, October 7, 2004

LOCATION: Room E40-298           TIME: 4:15pm

Reception immediately following in the
Philip M. Morse Reading Room, E40-106

SPEAKER

Professor Franz Rendl
University of Klagenfurt
Austria

TITLE

The Quadratic Assignment Problem

ABSTRACT

     The quadratic assignment problem (QAP) belongs to the hard core of NP-hard problems. It asks to minimize a quadratic function over the set of permutation matrices.

     Finding reasonable approximations to this problem is still a topic of current research. I will review several ways to get relaxations. These range from linear to semidefinite programming (SDP), from eigenvalue optimization to convex quadratic programming to copositive programming.

     There are several nontrivial connections among these relaxations, which have only been recognized recently. I will show some of these.

     I will also review the current computational state of the art to solve this problem. The best approximations currently seem to be based on SDP. Unfortunately, the resulting SDP are highly nontrivial to solve, as the primal matrix space as well as the dual space (determined by the primal constraints) grow rapidly (O(n^2) and O(n^4) respectively).

     I will conclude with some very recent computational methods that allow to deal with large scale problems of this type.

Joint work with: Henry Wolkowicz (Waterloo) and Renata Sotirov (Klagenfurt)\