regarding munkres function (Hungarian algorithm)

Now I know how to use the munkres function. But i want it to choose a certain way when there are many possible optimal solutions.

Example:

Initial_Matrix=
[4  3  4  5 
 4  3  4  5 
 6  1  2  3
 2  9  8  1]

Now there are 2 possible solutions :

1- (1,1) (2,2)(3,3)(4,4) with a total cost of 10

2- (2,1),(1,2)(3,3)(4,4) also total cost of 10

my 2 questions are:

Q1: I want the munkres function to favor the first solution ( that is, I want the lower row cell value to be assigned to a lower column cell value), in case there were multiple optimal solutions like the above. Is there a way to do that?

Q2: on what basis does the munkres function choose in case there were multiple optimal solutions just like the above ?

Answer 1

[Elad Kivelevitch]

Abbi,

You have a couple of options:

If you know for sure that a certain solution should be favored, you can deduct the cost of one of those elements by an eps. The total cost will be 10-eps and that would cause Munkres to choose that one.

c1 = % your matrix
c1(1) = c1(1)-1e-15;
assignmunkres(c1,10)
ans =

  4×2 uint32 matrix

   1   1
   3   2
   2   3
   4   4

The Munkres algorithm is described by the paper that Munkres wrote, please see the help/doc page.

You can use the other assignment functions we provide: matchpairs, assignjv, assignauction. These may return a different result when the cost is exactly the same. For example:

c1 = % your matrix
assignjv(c1,10)
ans =

  4×2 uint32 matrix

   1   1
   2   3
   3   2
   4   4

However, the most robust is to simply look at more than optimal solution. You can use assignkbest. This algorithm uses Murti's algorithm to return the top k optimal solutions. For example:

[assignments, ~, ~, cost] = assignkbest(c, 10, 5)

Returns the following result:

assignments =

  5×1 cell array

    {4×2 uint32}
    {4×2 uint32}
    {4×2 uint32}
    {4×2 uint32}
    {4×2 uint32}
    
cost =

    10
    10
    10
    10
    12

This indicates that there are 4 solutions with the exact same cost (10).