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

[Matt Haberland]

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200221/582f98b5/attachment.html>