Non-optimal results for test case with DBL_MAX in diagonal

[louiev]

The program generates the following results for the example matrix below:

Input cost matrix =
1.79769e+308 7.33184e+08 9.41561e+08 2.79247e+08
3.06449e+08 1.79769e+308 3.3464e+08 7.06878e+08
9.93296e+08 1.9414e+08 1.79769e+308 1.14174e+08
3.51623e+08 2.48635e+08 7.81242e+08 1.79769e+308
7.02639e+08 8.51663e+08 9.37382e+08 4.96945e+07
7.58851e+08 8.58445e+08 8.7235e+07 5.47076e+08

Munkres assignment =
-1 -1 -1 0
0 -1 -1 -1
-1 -1 -1 -1
-1 0 -1 -1
-1 -1 -1 -1
-1 -1 0 -1
Munkres cost = 9.21566e+08
= 3.06449e8 + 2.48635e8 + 8.7235e7 + 2.79247e8

Alternate assignment =
0 0 0 0
1 0 0 0
0 1 0 0
0 0 0 0
0 0 0 1
0 0 1 0
Alternate cost = 6.37518e+08
= 3.06449e8 + 1.9414e8 + 8.7235e7 + 4.96945e7

Munkres cost = 9.21566e+08
Alternate cost = 6.37518e+08

The input values were generated using

(rand() % 10^9) + 1.0

with DBL_MAX forcibly inserted into the diagonal.

The alternate and Munkres results match when the diagonal values are less than 3.0e24.

[louiev]

RAND_MAX = 2147483647 = 2^31 for this example.

[Gluttton]

Your comment seems reasonable, thank you for catching this!

I can reproduce the same result with your input data.
Here is the test which cover the issue:

TEST_F (MunkresTest, solve_6x4_NonObviousSolutionCase003_Success)
{
  // Arrange.
  Matrix<double> etalon_matrix{
    {-1.0, -1.0, -1.0, -1.0},
    { 0.0, -1.0, -1.0, -1.0},
    {-1.0,  0.0, -1.0, -1.0},
    {-1.0, -1.0, -1.0, -1.0},
    {-1.0, -1.0, -1.0,  0.0},
    {-1.0, -1.0,  0.0, -1.0}
  };
  Matrix<double> test_matrix{
    {1.79769e+308, 7.33184e+08,  9.41561e+08,  2.79247e+08},
    {3.06449e+08,  1.79769e+308, 3.3464e+08,   7.06878e+08},
    {9.93296e+08,  1.9414e+08,   1.79769e+308, 1.14174e+08},
    {3.51623e+08,  2.48635e+08,  7.81242e+08,  1.79769e+308},
    {7.02639e+08,  8.51663e+08,  9.37382e+08,  4.96945e+07},
    {7.58851e+08,  8.58445e+08,  8.7235e+07,   5.47076e+08}
  };

  Munkres<double> munkres;

  // Act.
  munkres.solve(test_matrix);

  // Assert.
  EXPECT_EQ (etalon_matrix, test_matrix);
}

I don't have the answer why this happened, but it looks like this is consequences of internal matrix resize which performed to convert non-square matrices to square (because algorithm works only for square matrices).

[louiev]

I have tried this with several non-square matrix sizes. As I understand it, the smaller dimension is mapped to "agents" and the other dimension is mapped to "jobs". The algorithm stops when each agent is mapped to a job, thus, there will be unassigned jobs.

I initially thought that the program was unable to handle double, so I changed the diagonal entry to FLT_MAX. That didn't pass either.

It seems to work when the diagonals are less than 3.0e24.

[Gluttton]

It looks like I have some progress.

If we add test for transposed matrix:

TEST_F (MunkresTest, solve_4x6_NonObviousSolutionCase004_Success)
{
  // Arrange.
  Matrix<double> etalon_matrix{
    {-1.0,  0.0, -1.0, -1.0, -1.0, -1.0},
    {-1.0, -1.0,  0.0, -1.0, -1.0, -1.0},
    {-1.0, -1.0, -1.0, -1.0, -1.0,  0.0},
    {-1.0, -1.0, -1.0, -1.0,  0.0, -1.0}
  };
  Matrix<double> test_matrix{
    {1.79769e+308, 3.06449e+08,  9.93296e+08,  3.51623e+08,  7.02639e+08,  7.58851e+08},
    {7.33184e+08,  1.79769e+308, 1.9414e+08,   2.48635e+08,  8.51663e+08,  8.58445e+08},
    {9.41561e+08,  3.3464e+08,   1.79769e+308, 7.81242e+08,  9.37382e+08,  8.7235e+07},
    {2.79247e+08,  7.06878e+08,  1.14174e+08,  1.79769e+308, 4.96945e+07,  5.47076e+08}
  };

  Munkres<double> munkres;

  // Act.
  munkres.solve(test_matrix);

  // Assert.
  EXPECT_EQ (etalon_matrix, test_matrix);
}

And run both tests solve_6x4_NonObviousSolutionCase003_Success and MunkresTest, solve_4x6_NonObviousSolutionCase004_Success we will get error only for one of them.

Also if we swap two lines in src/munkres.h:

        minimize_along_direction(matrix, false);
        minimize_along_direction(matrix, true);

broken test also will be changed!

[Gluttton]

I initially thought that the program was unable to handle double

The code handles doubles well.

It seems to work when the diagonals are less than 3.0e24.

I think this is because other items are about Xe08.

[Gluttton]

I've push changes which cover your input data. But I've found out other data sets for non-square matrices which performs with non-optimal result. So the issue shouldn't be closed yet.

[Gluttton]

After careful analysis of the issue, I'm pretty sure that the real problem is connected with non-square matrices but not with DBL_MAX. It would be logical to rename the issue, but since such issue already exists, I've decided close this issue and reopen the earlier.

P.S. Many thanks to @louiev for notice about the problem. As I can see he has joined to the GitHub specially to report the problem!