merge this supposedly faster method into scipy.optimize.linear_sum_assignment

[hrldcpr]

Seems to also implement the Hungarian algorithm, and is presumably better-maintained.

[hrldcpr]

Although as discussed in #4 theirs is maybe slower, so keep this alive until theirs has been improved? (And help with that?)

[hrldcpr]

9 also claims that this is faster than numpy, so I'm changing this issue to be about trying to figure out why and merge the faster version into numpy 🎉

[hrldcpr]

• [ ] benchmark this versus numpy to see if it actually is faster
• [ ] speed up numpy

[charnley]

Hi @hrldcpr , What is the status of this issue? The scipy's version is a pure python implementation https://github.com/scipy/scipy/blob/master/scipy/optimize/_hungarian.py

I think a lot of developers would benefit from a faster Hungarian implementation in scipy.

[hrldcpr]

Hi @charnley! Sadly there is zero progress on this.

Any interest in taking a look?! Either way, just bringing it back into my consciousness is helpful too, thanks!

I'll add a "help wanted" label which Github claims might cause it to be surfaced to people looking for something to do. But I'll also try to get to it myself by February, when I should have some free time.

[charnley]

I might have some time in January to look at it. At least I suggest adding it to a pip package so developers can just add it to requirements.txt for their Python projects.

[hrldcpr]

Cool if you get a chance that would be great!

And yes good point, making sure the pip version is working should be highest priority. Issue #12 is about that.

[berhane]

Hi All,

I benchmarked different linear assignment problem solvers you might find interesting.

• fully python implementations (munkres, scipy) and
• python wrappers to C/C++ implementations (hungarian, lap, lapjv) https://github.com/berhane/LAP-solvers

On Tue, Dec 4, 2018 at 11:46 AM harold cooper notifications@github.com wrote:

Cool if you get a chance that would be great!

And yes good point, making sure the pip version is working should be highest priority. Issue #12 https://github.com/hrldcpr/hungarian/issues/12 is about that.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/hrldcpr/hungarian/issues/5#issuecomment-444170172, or mute the thread https://github.com/notifications/unsubscribe-auth/AHG0ZpVDmCGUk9el8Zn0aEt1QOFK8JrSks5u1qb4gaJpZM4HdVPL .

[hrldcpr]

@berhane that's awesome, thanks! Looks like it would be even better to bake a LAPJV implementation into SciPy.

[berhane]

Thanks, @hrldcpr. Yes, the LAPJV seems to be the best overall performer. I'll contact the developers and see if they have interest including their implementation in SciPy.

[vmarkovtsev]

Hi, src-d/lapjv's author here. I am definitely interested in porting to SciPy.

Here are some random facts:

1. My lapjv is the same algorithm as lap, apart from the SIMD optimizations. It's theoretical computational complexity is the same as Hungarian's (cubic), which can be seen on the log plot in LAP-solvers.
2. The paper which describes the algorithm is behind a paywall but I can send it by request via email.
3. C/C++ code can be somewhat painlessly ported to pure Python, cython or numba, though it will obviously not reach the same peak performance.

So let's decide what I should code and I will code it 😄

[hrldcpr]

@vmarkovtsev Awesome, sounds perfect!

I think the very first step is that someone should figure out how people contribute to SciPy, and then maybe open a placeholder issue (if that's their methodology) and link to that from here.