ENH: Implement a Quadratic Assignment Problem Solver
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 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
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@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
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@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.
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: 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@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@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
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_s...> 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: 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@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@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
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 <https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_s...> 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: 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@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@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
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@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_s...> 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: 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@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@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
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<mailto: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<https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_s...> 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<mailto:ralf.gommers@gmail.com>> wrote: On Fri, Feb 21, 2020 at 2:03 AM Emanuele Olivetti <olivetti@fbk.eu<mailto: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: 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@jhu.edu<mailto:asaadel1@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@python.org<mailto: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<mailto:SciPy-Dev@python.org> https://mail.python.org/mailman/listinfo/scipy-dev _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org<mailto:SciPy-Dev@python.org> https://mail.python.org/mailman/listinfo/scipy-dev _______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org<mailto:SciPy-Dev@python.org> https://mail.python.org/mailman/listinfo/scipy-dev
On Fri, Feb 21, 2020 at 9:26 PM Ali Saad-Eldin <asaadel1@jhu.edu> wrote:
Hi all, [...]
Also, it could accept sparse inputs but the first steps of the algorithm
operate on dense arrays.
Same for DSPFP. Emanuele -- -- 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.
On Tue, Feb 25, 2020 at 3:17 AM Emanuele Olivetti <olivetti@fbk.eu> wrote:
On Fri, Feb 21, 2020 at 9:26 PM Ali Saad-Eldin <asaadel1@jhu.edu> wrote:
Hi all, [...]
Also, it could accept sparse inputs but the first steps of the algorithm
operate on dense arrays.
Same for DSPFP.
Sounds good to me. Cheers, Ralf
Emanuele
-- 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
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 <https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_s...> 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: 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@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@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.
I would follow the example of linear_sum_assignment <https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_s...>. 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 <https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_s...> 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: 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@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@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
participants (6)
-
Ali Saad-Eldin -
Emanuele Olivetti -
Kai Striega -
Matt Haberland -
Ralf Gommers -
Søren Fuglede Jørgensen