Title: Semidefinite Programming + Bundle Method: the Strongest Available Bounds for the Quadratic Assignment Problem

Semidefinite Programming (SDP) has proven to be very successful in providing tight relaxations for hard combinatorial problems. The nature of the Quadratic Assignment Problem (QAP) suggests SDP as a way to derive tractable relaxations. The seminar will explore several SDP relaxations of the QAP with increasing levels of complexity. Each of the relaxations contains a huge number of constraints that makes it very strong, but difficult to solve. The Bundle Method turns out to be a convenient method for dealing with such problems, since computations of the bounds include only selected constraints. The seminar will demonstrate the efficiency of the approach and, in particular, will address the following questions:
How are the relaxations derived?
Which constrains are selected?
How strong are the obtained lower bounds?
Can these lower bounds be implemented into a branch and bound framework for computing optimal solutions?