quadratic_assignment(A, B, method='faq', options=None)

Quadratic assignment solves problems of the following form:

$$\min_P & \ {\ \text{trace}(A^T P B P^T)}\\ \mbox{s.t. } & {P \ \epsilon \ \mathcal{P}}\\$$

where $\mathcal{P}$ is the set of all permutation matrices, and $A$ and $B$ are square matrices.

Graph matching tries to maximize the same objective function. This algorithm can be thought of as finding the alignment of the nodes of two graphs that minimizes the number of induced edge disagreements, or, in the case of weighted graphs, the sum of squared edge weight differences.

Note that the quadratic assignment problem is NP-hard. The results given here are approximations and are not guaranteed to be optimal.

Notes

The default method 'faq' <optimize.qap-faq> uses the Fast Approximate QAP algorithm ; it typically offers the best combination of speed and accuracy. Method '2opt' <optimize.qap-2opt> can be computationally expensive, but may be a useful alternative, or it can be used to refine the solution returned by another method.

Parameters

A : 2-D array, square

The square matrix $A$ in the objective function above.

B : 2-D array, square

The square matrix $B$ in the objective function above.

method : str in {'faq', '2opt'} (default: 'faq')

The algorithm used to solve the problem. 'faq' <optimize.qap-faq> (default) and '2opt' <optimize.qap-2opt> are available.

options : dict, optional

A dictionary of solver options. All solvers support the following:

maximize

maximize

partial_match

partial_match

rng

rng

If seed is None (or :None:None:`np.random`), the numpy.random.RandomState singleton is used. If seed is an int, a new RandomState instance is used, seeded with seed . If seed is already a Generator or RandomState instance then that instance is used.

For method-specific options, see show_options('quadratic_assignment') <show_options> .

Returns

res : OptimizeResult

OptimizeResult containing the following fields.

col_ind

col_ind

fun

fun

nit

nit

Approximates solution to the quadratic assignment problem and the graph matching problem.

Examples

>>> from scipy.optimize import quadratic_assignment
... A = np.array([[0, 80, 150, 170], [80, 0, 130, 100],
...               [150, 130, 0, 120], [170, 100, 120, 0]])
... B = np.array([[0, 5, 2, 7], [0, 0, 3, 8],
...               [0, 0, 0, 3], [0, 0, 0, 0]])
... res = quadratic_assignment(A, B)
... print(res)
 col_ind: array([0, 3, 2, 1])
     fun: 3260
     nit: 9

The see the relationship between the returned col_ind and fun , use col_ind to form the best permutation matrix found, then evaluate the objective function $f(P) = trace(A^T P B P^T )$ .

>>> perm = res['col_ind']
... P = np.eye(len(A), dtype=int)[perm]
... fun = np.trace(A.T @ P @ B @ P.T)
... print(fun)
3260

Alternatively, to avoid constructing the permutation matrix explicitly, directly permute the rows and columns of the distance matrix.

>>> fun = np.trace(A.T @ B[perm][:, perm])
... print(fun)
3260

Although not guaranteed in general, quadratic_assignment happens to have found the globally optimal solution.

>>> from itertools import permutations
... perm_opt, fun_opt = None, np.inf
... for perm in permutations([0, 1, 2, 3]):
...     perm = np.array(perm)
...     fun = np.trace(A.T @ B[perm][:, perm])
...     if fun < fun_opt:
...         fun_opt, perm_opt = fun, perm
... print(np.array_equal(perm_opt, res['col_ind']))
True

Here is an example for which the default method, 'faq' <optimize.qap-faq> , does not find the global optimum.

>>> A = np.array([[0, 5, 8, 6], [5, 0, 5, 1],
...               [8, 5, 0, 2], [6, 1, 2, 0]])
... B = np.array([[0, 1, 8, 4], [1, 0, 5, 2],
...               [8, 5, 0, 5], [4, 2, 5, 0]])
... res = quadratic_assignment(A, B)
... print(res)
 col_ind: array([1, 0, 3, 2])
     fun: 178
     nit: 13

If accuracy is important, consider using '2opt' <optimize.qap-2opt> to refine the solution.

>>> guess = np.array([np.arange(len(A)), res.col_ind]).T
... res = quadratic_assignment(A, B, method="2opt",
...                            options = {'partial_guess': guess})
... print(res)
 col_ind: array([1, 2, 3, 0])
     fun: 176
     nit: 17

See :

Back References

The following pages refer to to this document either explicitly or contain code examples using this.

scipy.optimize scipy.optimize._qap.quadratic_assignment scipy.optimize._optimize.show_options

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them

---

GitHub : /scipy/optimize/_qap.py#11
type: <class 'function'>
Commit: