Hi All, Since the inputs are graphs and the functionality resembles things that
live in scipy.sparse.csgraph, I'm wondering whether this either should go into sparse.csgraph or if it's better in scipy.optimize then should it be able to understand sparse inputs?
I'd say a QAP solver fits into scipy.optimize better than scipy.sparse.csgraph. We already have scipy.optimize.linear_sum_assignment <https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_s...> and an *"assignment problems"* category, although right, now it's a subcategory of linear programming. I also vaguely remember talk of a general quadratic programming solver to follow the linear programming solver, although I don't think there has been any progress there. Further, a QAP solver can be formulated as a more general quadratic programming problem, while the algorithms in csgraph all look like "classic" graph theory algorithms. Saying that, I haven't worked with csgraph much, so I may be wrong regarding its scope. Just adding my 2c Kai On Fri, 21 Feb 2020 at 20:14, Ralf Gommers <ralf.gommers@gmail.com> wrote:
On Fri, Feb 21, 2020 at 2:03 AM Emanuele Olivetti <olivetti@fbk.eu> wrote:
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@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
Since the inputs are graphs and the functionality resembles things that live in scipy.sparse.csgraph, I'm wondering whether this either should go into sparse.csgraph or if it's better in scipy.optimize then should it be able to understand sparse inputs?
Cheers, Ralf
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@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. _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev