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

Question

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

jvlmdr opened this issue 5 years ago · 7 comments

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.

Answer 1 · 2020-02-01T20:58:25.000Z

Hi, the cost matrix must be non-negative.

Do you see the error with cost + 30?

Answer 2 · 2020-02-01T21:17:01.000Z

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

Answer 3 · 2020-02-01T21:18:04.000Z

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

Answer 4 · 2020-02-01T22:08:23.000Z

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

Answer 5 · 2020-02-02T12:04:50.000Z

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.)

Answer 6 · 2020-02-13T21:24:50.000Z

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

Answer 7 · 2020-02-13T21:27:09.000Z

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?