# Quadratic programming problem involving permutation matrices

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem?

Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation matrices $P$.

I have heard that there are several types of algorithms for these kinds of problems, like iterative improvement, simulated annealing, tabu search, genetic algorithms, evolution strategies, ant algorithms, and scatter search. I am looking for existing software.

• How big are the matrices $A$ and $B$, typically? – Geoff Oxberry Dec 26 '13 at 20:43
• For vertex-ordering problems: for theoretical results try Flow Metrics (LP-based algorithms, subsequent theoretical improvements use SDPs). In practice, in my experience, the best approach for our problems was to use METIS (or in our case H-METIS) as the basis of a divide-and-conquer algorithm (nearly linear time), followed by iterations of local improvement. But that might not work for you depending on A and B. – Neal Young Dec 27 '13 at 0:18
• What norm is this? I can think of a few thinks for $||A||$: least squares, max, etc. – john mangual Dec 27 '13 at 19:14
• Thanks a lot for the answer, I will check METIS. The matrices will be up to 500 by 500. I will probably try with a few different norms and see what works best in my case. – user12383 Dec 27 '13 at 21:40
• This is a combinatorial problem, not a quadratic program. The feasible set contains $n!$ elements. You're probably stuck with some heuristic to solve it. – Dominique Dec 28 '13 at 0:05