Optimisations for rectangular matrices

Hi,

I was looking for a fast linear assignment solver and came across this project. Great work! Thank you.

It compares well against Scipy's linear_sum_assignment on square matrices, but is significantly worse on rectangular matrices.
The implementation appears to not support rectangular matrices out of the box, so to test it against Scipy I padded the cost matrix with high values to make it square.

In this setting the algorithm this implementation was much slower than the Scipy implementation on rectangular matrices (and still faster than Scipy implementation on the padded matrix).

I was wondering if the this algorithm could be made to work efficiently on rectangular matrices, or whether there are perhaps some fundamental limitations that would prevent this.

Thanks,
Alexey

Start by benchmarking the linear assignment solver on rectangular matrices and compare the results with scipy's linear_sum_assignment, as described in the issue. The issue names no source files or tests, so locate the solver entry point and existing square-matrix benchmarks first. Done means rectangular matrices are supported efficiently without relying on padding.