« search calendars« DIMACS Workshop on Optimization in Distance Geometry

« Clique-Based Semidefinite Relaxation of the Quadratic Assignment Problem

Clique-Based Semidefinite Relaxation of the Quadratic Assignment Problem

June 26, 2019, 4:20 PM - 5:00 PM



Rutgers University

CoRE Building

96 Frelinghuysen Road

Piscataway, NJ 08854

Click here for map.

Yuehaw Khoo, Stanford University

The matching problem between two adjacency matrices, A and B, can be formulated as the NP-hard quadratic assignment problem (QAP). While the QAP admits a semide nite (SDP) relaxation that is often tight in practice, this SDP scales badly as it involves a matrix variable of size n2 by n2. To achieve a speed up, a further relaxation of the SDP will be described, where the number of variables scale as O(bn2), where b is the number of non-zero entries in B. The dual problem of this relaxation has a natural three-block structure that can be solved via Alternating Direction Method of Multipliers (ADMM) in a distributed manner. I will show results that suggest this relaxation o ers a good compromise between speed and tightness in practice, and will discuss how the assignment problem in Nuclear Magnetic Resonance Spectroscopy can be formulated as a QAP with sparse B.

This is joint work with Jose Simoes Bravo Ferreira and Amit Singer.