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

Thu Feb 27 02:22:26 EST 2020

I would follow the example of linear_sum_assignment
<https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html>.
For QAP, it looks like the only difference would be that you'd need two
input matrices (weights and distances).

On Wed, Feb 26, 2020 at 4:02 AM Emanuele Olivetti <olivetti at fbk.eu> wrote:

> Hi Ali and Everyone interested in this topic,
>
> What API would be OK for SciPy, for algorithms about QAP/GMP?
>
> @Ali: I see that your implementation of the FAQ algorithm follows the
> .fit() / .fit_predict() pattern of scikit-learn. In my case, with DSPFP, it
> is something very basic and not thought for a proper API. I can change it
> though. Moreover, I still don't have proper tests. Ideas? Comments?
>
> Best,
>
> Emanuele
>
>
> On Fri, Feb 21, 2020 at 9:26 PM Ali Saad-Eldin <asaadel1 at jhu.edu> wrote:
>
>> 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> 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>
>> wrote:
>>
>>
>>
>> On Fri, Feb 21, 2020 at 2:03 AM Emanuele Olivetti <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> 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
>> 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
>> https://mail.python.org/mailman/listinfo/scipy-dev
>>
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at python.org
>> https://mail.python.org/mailman/listinfo/scipy-dev
>>
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at python.org
>> https://mail.python.org/mailman/listinfo/scipy-dev
>>
>> _______________________________________________
>> 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.
>

-- 
Matt Haberland
Assistant Professor
BioResource and Agricultural Engineering
08A-3K, Cal Poly
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200226/7b2da9fc/attachment-0001.html>