I would like to add a
Quadratic Approximation
Problem (QAP) solver function, by implementing the
Fast
Approximate QAP (FAQ) algorithm (Vogelstein, 2015). QAP is a combinatorial optimization problem, and the FAQ algorithm can be applied to solve special cases of QAP, including the Graph Matching Problem (GMP) and the Traveling Salesman Problem (TSP).
Since the QAP is a combinatorial optimization problem, I'd like to have the FAQ implementation exposed through scipy.optimize. The module would accept parameters such as permutation initialization type (single barycenter initialization,
or several initializations "close" to the barycenter), maximum Frank-Wolfe iterations, and whether you would like to solve a special case of the QAP (such as GMP). The module would fit with the two cost matrices in the objective function, returning the score
(minimized objection function value) and indices of the optimal permutation matrix from the objective function. The implementation will also give the option to include seeds
I have already implemented FAQ in
GraSPy,
and proof of effectiveness can be found
here .