quadratic_assignment(method=’2opt’)¶

scipy.optimize.
quadratic_assignment
(A, B, method='2opt', options={'maximize': False, 'rng': None, 'partial_match': None, 'partial_guess': None}) Solve the quadratic assignment problem (approximately).
This function solves the Quadratic Assignment Problem (QAP) and the Graph Matching Problem (GMP) using the 2opt algorithm [1].
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 NPhard. The results given here are approximations and are not guaranteed to be optimal.
 Parameters
 A2D array, square
The square matrix \(A\) in the objective function above.
 B2D array, square
The square matrix \(B\) in the objective function above.
 methodstr in {‘faq’, ‘2opt’} (default: ‘faq’)
The algorithm used to solve the problem. This is the methodspecific documentation for ‘2opt’. ‘faq’ is also available.
 Returns
 resOptimizeResult
OptimizeResult
containing the following fields. col_ind1D 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.
See also
For documentation for the rest of the parameters, see
scipy.optimize.quadratic_assignment
 Options
 maximizebool (default: False)
Maximizes the objective function if
True
. rngint, RandomState, Generator or None, optional (default: None)
Accepts an integer as a seed for the random generator or a
RandomState
orGenerator
object. If None (default), uses globalnumpy.random
random state. partial_match2D 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)
, wherem
is not greater than the number of nodes, \(n\). partial_guess2D array of integers, optional (default: None)
A guess for the matching between the two matrices. Unlike partial_match, partial_guess does not fix the indices; they are still free to be optimized.
Each row of partial_guess specifies a pair of matched nodes: node
partial_guess[i, 0]
of A is matched to nodepartial_guess[i, 1]
of B. The array has shape(m, 2)
, wherem
is not greater than the number of nodes, \(n\).
Notes
This is a greedy algorithm that works similarly to bubble sort: beginning with an initial permutation, it iteratively swaps pairs of indices to improve the objective function until no such improvements are possible.
References
 1
“2opt,” Wikipedia. https://en.wikipedia.org/wiki/2opt
 2
D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski, C. Priebe, “Seeded graph matching”, Pattern Recognit. 87 (2019): 203215, https://doi.org/10.1016/j.patcog.2018.09.014