I would follow the example of linear_sum_assignment. 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@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@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@python.org> on behalf of Matt Haberland <mhaberla@calpoly.edu>
Sent: Friday, February 21, 2020 9:21 AM
To: SciPy Developers List <scipy-dev@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@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 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:

Best,

Emanuele

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) solver function, by implementing the Fast Approximate QAP (FAQ) algorithm (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, and proof of effectiveness can be found here .

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
_______________________________________________
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

--
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