search

gatagat / lap

Linear Assignment Problem solver (LAPJV/LAPMOD).
BSD 2-Clause "Simplified" License
211 stars 66 forks source link

Extension of non-square matrix with all negative values in lapjv #21

Open jvlmdr opened 4 years ago

jvlmdr commented 4 years ago

Hey, I think there is a bug in the code for extending a non-square matrix to a square matrix.

Consider the all-negative cost matrix

[[2, 4, 6, 8], [1, 2, 4, 8]] - 30

with values in the range [-30, -20].

The minimal cost should be 2 + 2 + -30 * 2 = -56 but lapjv returns 0. The indices of the solution are all -1.

gatagat commented 4 years ago

Hi, the cost matrix must be non-negative.

Do you see the error with cost + 30?

jvlmdr commented 4 years ago

Oh ok, sorry, I didn't realise :)

jvlmdr commented 4 years ago

And yep, it gives the correct solution for the positive cost matrix.

gatagat commented 4 years ago

This should definitely be mentioned in the docs. If you have some time, please, send a PR.

jvlmdr commented 4 years ago

Maybe it would be better to also raise an exception if one of the costs is negative, or subtract the minimum? But are you sure it doesn't work with negative costs? It seems to give the correct result, although I haven't tested it extensively. (The modification that I proposed in https://github.com/gatagat/lap/pull/22 was only to fix an issue with the extension to a square cost matrix when all of the costs were negative.)

gatagat commented 4 years ago

@jvlmdr You are right, my bad, lack of sleep, lack of time... It is the dual where the reduced costs have to be non-negative, so no issue in the algorithm itself, the extension is wrong.

gatagat commented 4 years ago

And your patch #22 is sound. The only question that remains is what has a better runtime: extend the way you do, or shift the costs to zero first and extend as before?