ENH: Add an approximate Linear Sum Assignment Solver
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_s...>, 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(n2.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_cod...>. Best, Ali Saad-Eldin
On Fri, Jul 10, 2020 at 4:03 PM Ali Saad-Eldin <asaadel1@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_s...>, 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_cod...> .
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
participants (2)
-
Ali Saad-Eldin -
Ralf Gommers