[SciPy-Dev] ENH: Add an approximate Linear Sum Assignment Solver

[Ralf Gommers]

On Fri, Jul 10, 2020 at 4:03 PM Ali Saad-Eldin <asaadel1 at jhu.edu> wrote:

> Hi all,
> Hi all,
>
> I would like to add an approximate Linear Assignment Problem
> <http://www.assignmentproblems.com/doc/LSAPIntroduction.pdf> (aLAP)
> solver to scipy.optimize. The specific approximation algorithm I propose
> adding can be found here
> <https://link.springer.com/content/pdf/10.1007%2F978-3-540-68111-3_74.pdf>.
> Scipy.optimize currently houses an exact solver for LAP in
> linear_sum_assignment()
> <https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html>,
> and I was thinking this could be added either as a new method within
> linear_sum_assignment(), or as its own function.
>
> The approximation algorithm has time complexity O(n2log(n)), compared to
> the algorithm implemented in linear_sum_assignment() with complexity ~O(n
> 2.3 ), while guaranteeing a score >= 1/2 optimum (though in practice the
> scores appear to be much closer to optimum).   I've attached two plots
> demonstrating runtime and accuracy, running linear_sum_assignment() and
> aLAP on simulated, dense nxn cost_matrices with entries randomly selected
> from a uniform(0,100) distribution, for n sampled from [0, 3000]. Note that
> linear_sum_assignment() is essentially C/C++, while the aLAP implementation
> is native Python, so a cython implementation could make aLAP even faster.
> Additionally, an advantage to this algorithm is that it is parallelizable,
> which could cause a further speed up.
>
> Current version of the implementation can be found here
> <https://github.com/neurodata/graspy/blob/ase-alap/graspy/match/alap.py>,
> and proof of effectiveness here
> <https://nbviewer.jupyter.org/github/asaadeldin11/nbview/blob/master/aLAP_code.ipynb>
> .
>

Hi Ali, thanks for proposing this! Just so this email doesn't go completely
unanswered: this seems interesting. As you noticed, we're (more than a
little) short on reviewer power, so this may be hard to do in parallel with
your Quadratic Assignment Solver in https://github.com/scipy/scip/pull/11862
.

Cheers,
Ralf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200804/712bc982/attachment.html>