Abstract
The Quadratic Assignment Problem (QAP) is an important discrete optimization instance that encompasses many well-known combinatorial optimization problems, and has applications in a wide range of areas such as logistics and computer vision. The QAP, unfortunately, is NP-hard to solve. To address this difficulty, a number of semidefinite relaxations of the QAP have been developed. These techniques are known to be powerful in that they compute globally optimal solutions in many instances, and are often deployed as sub-routines within enumerative procedures for solving QAPs. In this paper, we investigate the strength of these semidefinite relaxations. Our main result is a deterministic set of conditions on the input matrices -- specified via linear inequalities -- under which these semidefinite relaxations are exact. Our result is simple to state, in the hope that it serves as a foundation for subsequent studies on semidefinite relaxations of the QAP as well as other related combinatorial optimization problems. As a corollary, we show that the semidefinite relaxation is exact under a perturbation model whereby the input matrices differ by a suitably small perturbation term. One technical difficulty we encounter is that the set of dual feasible solutions is not closed. To circumvent these difficulties, our analysis constructs a sequence of dual feasible solutions whose objective value approaches the primal objective, but never attains it.
Introduction
The Quadratic Assignment Problem (QAP) remains one of the most challenging problems in combinatorial optimization. In its classic formulation, one must assign $n$ facilities to $n$ locations, minimizing the total cost derived from the product of flows between facilities and distances between locations. Due to its NP-hard nature, finding global optima for even moderate sizes (e.g., $n=50$) is a significant computational feat.
To tackle this, researchers frequently employ Semidefinite Programming (SDP) relaxations. These methods "relax" the discrete constraints of a permutation into a convex set, allowing for efficient optimization. While these relaxations are empirically successful, the theoretical conditions under which they are guaranteed to be exact—meaning the relaxation returns the true discrete solution—have remained elusive. This paper provides a deterministic framework to identify these "easy" instances of the QAP.
The Master Theorem and Linear Conditions
The primary contribution of this work is the "Master Theorem" (Theorem 3.1), which establishes a set of deterministic conditions on the input matrices $A$ and $B$. Unlike previous literature that often relied on complex spectral conditions (such as requiring distinct eigenvalues), this theorem utilizes simple linear inequalities.
If a collection of vectors can be found that satisfy these specific inequalities relative to the entries of $A$ and $B$, the SDP relaxation is guaranteed to be exact. This shift toward linearity not only simplifies the theoretical statement but also provides a more practical "certificate" that can be checked for specific problem instances.
Overcoming the Dual Gap
A significant technical hurdle in proving exactness for QAP relaxations is the behavior of the dual problem. The authors identify that the set of dual feasible solutions is not "closed," a phenomenon referred to as a spectrahedral shadow. In such cases, a single optimal dual solution may not exist on the boundary of the feasible set.
To circumvent this, the analysis employs a sequence construction. By building a sequence of dual feasible solutions that asymptotically approach the primal objective value, the authors prove exactness even when a standard solution cannot be attained. This discovery explains why previous attempts to prove exactness using standard duality arguments may have struggled to reach a definitive conclusion.
Experimental Validation
The theoretical findings were validated through two distinct numerical experiments:
- Graph Matching: The authors tested the relaxation on all non-isomorphic graph pairs for small dimensions. For $n \le 5$, the relaxation was 100% exact. At $n=6$, involving over 12,000 pairs, the exactness remained high at 94.5%, though the authors identified specific counter-examples where the relaxation fails.
- Distance Matrices: Using Euclidean distance matrices generated from random 3D Gaussian point clouds, the relaxation demonstrated remarkable robustness. It maintained 99% exactness even at $n=10$.
Furthermore, the "Master Theorem" conditions were found to be highly applicable; in instances where the relaxation was exact, the required certificate vectors were successfully identified in 91% to 100% of cases.
Key Insights and Implications
Several important observations emerge from this study:
- The $n=3$ Milestone: The authors prove that for $n=3$, this specific SDP relaxation is always exact, regardless of the input matrices.
- Structure and Geometry: The relaxation performs significantly better on structured data, such as distance matrices, than on generic random matrices. This suggests that real-world problems, which often possess underlying geometric structure, are inherently more amenable to SDP relaxations than worst-case theoretical models.
- Exactness vs. Uniqueness: While the theorem guarantees that the objective value of the relaxation matches the QAP, it does not guarantee a unique permutation. In some instances, the solver may return a convex combination of multiple optimal permutations.
Conclusion
By providing a deterministic set of conditions for exactness, this work bridges the gap between the theoretical complexity of the QAP and the practical utility of SDP relaxations. While the existence of counter-examples at $n=6$ for graph matching indicates that the relaxation is not a universal solution, the high success rate on structured data provides a strong foundation for using these methods in logistics, computer vision, and beyond.
Summary updated