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

Fri Feb 21 15:11:22 EST 2020

Hi all,
I agree with both Kai and Matt. Since the QAP is a combinatorial optimization problem (even though it has graph theory applications), and that there is already an "assignment problem" category in scipy.optimize, I think a QAP solver would fit better there. Also, it could accept sparse inputs but the first steps of the algorithm operate on dense arrays.
Best,
Ali
________________________________
From: SciPy-Dev <scipy-dev-bounces+asaadel1=jhu.edu at python.org> on behalf of Matt Haberland <mhaberla at calpoly.edu>
Sent: Friday, February 21, 2020 9:21 AM
To: SciPy Developers List <scipy-dev at python.org>
Subject: Re: [SciPy-Dev] ENH: Implement a Quadratic Assignment Problem Solver

I can't say where it would fit better, but it sounds like QAP would fit well in optimize next to linear_sum_assignment now and the more general MIP and QP solvers when they happen.

On Fri, Feb 21, 2020, 5:27 AM Kai Striega <kaistriega at gmail.com<mailto:kaistriega at gmail.com>> wrote:
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_sum_assignment.html#scipy.optimize.linear_sum_assignment> 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 at gmail.com<mailto:ralf.gommers at gmail.com>> wrote:

On Fri, Feb 21, 2020 at 2:03 AM Emanuele Olivetti <olivetti at fbk.eu<mailto:olivetti at 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 at jhu.edu<mailto: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

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 at python.org<mailto: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.
_______________________________________________
SciPy-Dev mailing list
SciPy-Dev at python.org<mailto:SciPy-Dev at python.org>
https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________
SciPy-Dev mailing list
SciPy-Dev at python.org<mailto:SciPy-Dev at python.org>
https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________
SciPy-Dev mailing list
SciPy-Dev at python.org<mailto:SciPy-Dev at python.org>
https://mail.python.org/mailman/listinfo/scipy-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200221/1374648c/attachment-0001.html>