quadratic_assignment — SciPy v1.15.2 Manual (original) (raw)

scipy.optimize.

scipy.optimize.quadratic_assignment(A, B, method='faq', options=None)[source]#

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

Quadratic assignment solves problems of the following form:

\[\begin{split}\min_P & \ {\ \text{trace}(A^T P B P^T)}\\ \mbox{s.t. } & {P \ \epsilon \ \mathcal{P}}\\\end{split}\]

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.

Parameters:

A2-D array, square

The square matrix \(A\) in the objective function above.

B2-D array, square

The square matrix \(B\) in the objective function above.

methodstr in {‘faq’, ‘2opt’} (default: ‘faq’)

The algorithm used to solve the problem.‘faq’ (default) and‘2opt’ are available.

optionsdict, optional

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

maximizebool (default: False)

Maximizes the objective function if True.

partial_match2-D array of integers, optional (default: None)

Fixes part of the matching. Also known as a “seed” [2].

Each row of partial_match specifies a pair of matched nodes: node partial_match[i, 0] of A is matched to nodepartial_match[i, 1] of B. The array has shape (m, 2), where m is not greater than the number of nodes, \(n\).

rngnumpy.random.Generator, optional

Pseudorandom number generator state. When rng is None, a newnumpy.random.Generator is created using entropy from the operating system. Types other than numpy.random.Generator are passed to numpy.random.default_rng to instantiate a Generator.

Changed in version 1.15.0: As part of the SPEC-007transition from use of numpy.random.RandomState tonumpy.random.Generator is occurring. Supplying_np.random.RandomState_ to this function will now emit a_DeprecationWarning_. In SciPy 1.17 its use will raise an exception. In addition relying on global state using np.random.seed_will emit a FutureWarning. In SciPy 1.17 the global random number generator will no longer be used. Use of an int-like seed will raise a FutureWarning, in SciPy 1.17 it will be normalized via np.random.default_rng rather than_np.random.RandomState.

For method-specific options, seeshow_options('quadratic_assignment').

Returns:

resOptimizeResult

OptimizeResult containing the following fields.

col_ind1-D array

Column indices corresponding to the best permutation found of the nodes of B.

funfloat

The objective value of the solution.

nitint

The number of iterations performed during optimization.

Notes

The default method ‘faq’ uses the Fast Approximate QAP algorithm [1]; it typically offers the best combination of speed and accuracy. Method ‘2opt’ can be computationally expensive, but may be a useful alternative, or it can be used to refine the solution returned by another method.

References

[1]

J.T. Vogelstein, J.M. Conroy, V. Lyzinski, L.J. Podrazik, S.G. Kratzer, E.T. Harley, D.E. Fishkind, R.J. Vogelstein, and C.E. Priebe, “Fast approximate quadratic programming for graph matching,” PLOS one, vol. 10, no. 4, p. e0121002, 2015,DOI:10.1371/journal.pone.0121002

[2]

D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski, C. Priebe, “Seeded graph matching”, Pattern Recognit. 87 (2019): 203-215, DOI:10.1016/j.patcog.2018.09.014

Examples

import numpy as np from scipy.optimize import quadratic_assignment rng = np.random.default_rng() 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, options={'rng': rng}) print(res) fun: 3260 col_ind: [0 3 2 1] 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’, 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, options={'rng': rng}) print(res) fun: 178 col_ind: [1 0 3 2] nit: 13

If accuracy is important, consider using ‘2opt’to refine the solution.

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