MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

A New SDP Relaxation for the Quadratic Assignment Problem

Maximilian John
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Thursday, 31 March 2016
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

The quadratic assignment problem (QAP) is one of the hardest combinatorial optimization problems.

Its range of applications is wide, including facility location, keyboard layout, and various other domains.
The key success factor of specialized branch-and-bound frameworks for minimizing QAPs is an efficient implementation of a strong lower bound.
In this talk, we propose a lower-bound preserving transformation of a QAP to a different quadratic problem allowing for small and efficiently solvable SDP relaxations. This transformation is self-tightening in a branch-and-bound process. Experimental evaluations show promising results, in particular for instances with a small width in one of the dimensions.

Contact

Maximilian John
--email hidden
passcode not visible
logged in users only

Maximilian John, 03/31/2016 00:16
Maximilian John, 02/02/2016 09:25 -- Created document.