Scipy - Linear Sum Assignment - Show the Workings

6.2k views Asked by At

I am trying to learn various implementations of the Hungarian Algorithm. Specifically, I want to maximise and get the highest score.

I have found two solutions from various packages: (1) the munkres package, and (2) Linear Sum Assignment in Scipy

(1) http://software.clapper.org/munkres/ (2) https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

I was able to get something together with #1 but was finding issues in my implementation (https://github.com/bmc/munkres/issues/39). So, I am now trying to work with option #2.

Here is what I have so far:

import numpy as np
from scipy.optimize import linear_sum_assignment

matrix = np.array([
    [10.01,     10.02,  8.03,       11.04],
    [9.05,      8.06,   500.07,     1.08],
    [9.09,      7.11,   4.11,       1000.12]
])

row_ind, col_ind = linear_sum_assignment(matrix, maximize=True) 
print('\nSolution:', matrix[row_ind, col_ind].sum())

It returns the correct solution of 1510.21.

Help I would appreciate:

I have been struggling to display the workings. Ideally, what I want to see is the matching row and column pair and the score. In this example, it would be:

(0,1) (10.02)
(1,2) (500.07)
(2,3) (1000.12)

This was straight forward enough to do with the munkres package (#1 detailed above) but struggling to get my head around how to make this work with the scipy implementation.

Thanks for any help

1

There are 1 answers

0
lummers On

I was able to get what I was after using something like this:-

for i in range(len(row_ind)):
    print("row: ", row_ind[i], "  col: " ,col_ind[i], "  value: ", matrix[i, col_ind[i]] )

This will return the position in the matrix along with the value.