Friday, 29 September 2023

How to understand the output of scipy's quadratic_assignment function?

I'm trying to use scipy's quadratic_assignment function but I can't understand how the output can describe an optimal solution. Here is a minimal example where I compare a small matrix to itself:

import numpy as np
from scipy.optimize import quadratic_assignment

# Parameters
n = 5
p = np.log(n)/n   # Approx. 32%

# Definitions
A = np.random.rand(n,n)<p

# Quadratic assignment
res = quadratic_assignment(A, A)

print(res.col_ind)

and the results seem to be random assignments:

[3 0 1 4 2]
[3 2 4 1 0]
[3 2 1 0 4]
[4 3 1 0 2]
[2 3 0 1 4]
...

However, according to the docs col_ind is supposed to be the Column indices corresponding to the best permutation found of the nodes of B. Since the input matrices are equal (B==A), I would thus expect the identity assignment [0 1 2 3 4] to pop out. Changing n to larger values does not help.

Is there something I am getting wrong?



from How to understand the output of scipy's quadratic_assignment function?

No comments:

Post a Comment