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

[jvlmdr]

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]

Hi, the cost matrix must be non-negative.

Do you see the error with cost + 30?

[jvlmdr]

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

[jvlmdr]

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

[gatagat]

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

[jvlmdr]

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 #22 was only to fix an issue with the extension to a square cost matrix when all of the costs were negative.)

[gatagat]

@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]

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?