Issue with Floating Point Numbers

[LummersGit]

Hello.

First, let me write down some thanks. This is a nice, straight forward implementation. This is my first time dipping my toes into the water on linear programming and optimisation, so appreciate how accessible this is to set up and use.

That said, I am finding inconsistent behaviour. I am using the sample code from the project website (https://software.clapper.org/munkres/index.html).

Take these two example matrices. The only value I am changing is in position (1,2).

matrix = [
[10.01,     10.02,  8.03,       11.04],
[9.05,      8.06,   5000.07,     1.08],
[9.09,      7.11,   4.11,       1000.12]
]

Returns (expected)
(0,0) -> 10.01
(1,2) -> 5000.07
(2,3) -> 1000.12

matrix = [
[10.01,     10.02,  8.03,       11.04],
[9.05,      8.06,   500.07,     1.08],
[9.09,      7.11,   4.11,       1000.12]
]

Returns (unexpected):
(0,0) -> 10.01
(1,1) -> 8.06
(2,3) -> 1000.12

Why does the second matrix not return 10.01, 500.07, 1000.12?

I can see this issue at scale if I use a large sample size.

matrix = [
[0.233333333,	0.033333333,	0.013888889,	0.015384615,	0.032258065,	0.022222222,	0.033333333,	0.023255814,	0.01754386,	0.027027027],
[0.041666667,	0.035714286,	0.013888889,	0.015384615,	0.032258065,	0.022222222,	0.035714286,	0.023255814,	0.01754386,	0.027027027],
[0.021276596,	0.021276596,	0.013888889,	0.246153846,	0.212765957,	0.744680851,	0.021276596,	0.085106383,	0.105263158,	0.106382979],
[0.041666667,	0.035714286,	0.013888889,	0.030769231,	0.032258065,	0.2,	        0.428571429,	0.209302326,	0.01754386,	0.108108108],
[0.02173913,	0.02173913,	0.013888889,	0.030769231,	0.02173913,	0.043478261,	0.043478261,	0.760869565,	0.140350877,	0.043478261]
]

This simply default to returning locations (0,0), (1,1), (2,2), (3,3), (4,4). This is what I see when running my much larger sample, everything just incrementing through the matrix until the end.

To experiment, I ran the same larger data set but modified to multiple all values by 10,000 and round to nearest integer. That worked and didn't return the (0,0),(1,1), (2,2) result. Hence why I think it may be something to do with floats.

Hopefully not missing something silly at my end.

Thanks
Lummers

from munkres import Munkres, print_matrix
import sys

m = Munkres()

matrix = [
[10.01, 10.02,  8.03, 11.04],
[9.05,  8.06,  500.07, 1.08],
[9.09,  7.11,  4.11, 10.12]
]

cost_matrix = []

for row in matrix:
    cost_row = []
    for col in row:
        cost_row += [sys.maxsize - col]
    cost_matrix += [cost_row]

m = Munkres()


indexes = m.compute(cost_matrix)
# print_matrix(matrix, msg="hello")
total = 0

for row, column in indexes:
    value = matrix[row][column]
    total += value
    print(f'({row},{column}) -> {value}')

Here is my version info:

import sys
import munkres
print (munkres.__version__)
print(sys.version)
print(sys.version_info)

1.1.4
3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 23:11:46) [MSC v.1916 64 bit (AMD64)]
sys.version_info(major=3, minor=8, micro=1, releaselevel='final', serial=0)