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

Fri Feb 21 13:43:35 EST 2020

Hi all

Regarding where the implementation could live, let me also quickly note that in https://github.com/scipy/scipy/pull/10296#issuecomment-512850498, we had a bit of discussion on how a sparsity-friendly implementation of linear_sum_assignment could find a natural home in csgraph, perhaps as csgraph.minimum_weight_full_matching. (FWIW, I still haven't given up on solving the licensing issue mentioned in that thread, but let me use this discussion as an excuse to push for an update.) In that case, we would want to spell out the link between that algorithm and its scipy.optimize counterpart clearly in the documentation, to ensure discoverability. Similarly, in this case, if the QAP implementation ends up it csgraph, it would be useful to be able to find it through scipy.optimize somehow (would having a simple alias in scipy.optimize be overkill/confusing?)

Søren

On Fri, Feb 21, 2020 at 06:21:48AM -0800, Matt Haberland wrote:
> 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