A Continuous Variable Optimization Method for the Quadratic Assignment Problem

Abstract

We present a novel continuous algorithm for solving the Quadratic Assignment Problem (QAP), leveraging auxiliary dynamics to enforce permutation constraints without the need for post-processing. This approach outperforms traditional continuous methods in terms of constraint enforcement and demonstrates faster convergence compared to branch-and-bound techniques. Despite the algorithm's effectiveness, the number of auxiliary variables currently scales cubically with the problem size, posing a limitation. However, our analysis suggests that associating auxiliary variables with correlators of clause functions could significantly improve efficiency. Additionally, the algorithm encounters challenges with local minima due to the geodesically non-convex QAP potential. We propose future research directions to address this issue, including alternative formulations of the potential landscape and strategies for escaping local minima.