[SciPy-Dev] ENH: Implement a Quadratic Assignment Problem Solver

[Emanuele Olivetti]

Dear Ali and SciPy,

Some time ago, I implemented another algorithm for the approximate solution
of the QAP / Graph Matching: the Doubly Stochastic Projected Fixed-Point
(DSPFP) algorithm proposed in Lu et al. (2016) [*]. Input and output are
basically the same as the FAQ algorithm of Ali. If there is interest in
adding approximate QAP / Graph Matching algorithms to SciPy, I'd happy to
contribute with it:
  https://github.com/emanuele/DSPFP

Best,

Emanuele

[*] : http://dx.doi.org/10.1016/j.patcog.2016.07.015
Pre-print about the same manuscript and algorithm (named fastPFP at that
time, 2012) here: https://arxiv.org/abs/1207.1114

On Thu, Feb 20, 2020 at 6:38 PM Ali Saad-Eldin <asaadel1 at jhu.edu> wrote:

> Hello!
>
> I would like to add a Quadratic Approximation Problem (QAP)
> <https://en.wikipedia.org/wiki/Quadratic_assignment_problem> solver
> function, by implementing the Fast Approximate QAP (FAQ) algorithm
> <https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0121002&type=printable> (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
> <https://github.com/neurodata/graspy/blob/master/graspy/match/faq.py>,
> and proof of effectiveness can be found here
> <https://graspy.neurodata.io/tutorials/matching/faq.html> .
>
> Best,
> Ali Saad-Eldin
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev
>

-- 
--
Le informazioni contenute nella presente comunicazione sono di natura 
privata e come tali sono da considerarsi riservate ed indirizzate 
esclusivamente ai destinatari indicati e per le finalità strettamente 
legate al relativo contenuto. Se avete ricevuto questo messaggio per 
errore, vi preghiamo di eliminarlo e di inviare una comunicazione 
all’indirizzo e-mail del mittente.

--
The information transmitted is 
intended only for the person or entity to which it is addressed and may 
contain confidential and/or privileged material. If you received this in 
error, please contact the sender and delete the material.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200221/3e893343/attachment-0001.html>