Efficient Lifted Relaxations of the Quadratic Assignment Problem

Abstract

Quadratic assignment problems (QAPs) and quadratic assignment matchings (QAMs) recently gained a lot of interest in computer graphics and vision, e.g. for shape and graph matching. Literature describes several convex relaxations to approximate solutions of the NP-hard QAPs in polynomial time. We compare the convex relaxations recently introduced in computer graphics and vision to established approaches in discrete optimization. Building upon a unified constraint formulation we theoretically analyze their solution spaces and their approximation quality. Experiments on a standard benchmark as well as on instances of the shape matching problems support our analysis. It turns out that often the bounds of a tight linear relaxation are competitive with the bounds of semidefinite programming (SDP) relaxations, while the linear relaxation is often much faster to calculate. Indeed, for many instances the bounds of the linear relaxation are only slightly worse than the SDP relaxation of Zhao [ZKRW98,PR09], which itself is at least as accurate as the relaxations currently used in computer graphics and vision. Solving the SDP relaxations can often be accelerated considerably from hours to minutes using the recently introduced approximation method for trace bound SDPs [WSvdHT16], but nonetheless calculating linear relaxations is faster in most cases. For the shape matching problem all relaxations generate the optimal solution, only that the linear relaxation does so faster. Our results generalize as well to QAMs for which we deliver new relaxations. Furthermore by interpreting the Product Manifold Filter [VLR∗17] in the context of QAPs we show how to automatically calculate correspondences between shapes of several hundred points.