Kuhn-Munkres algorithm (Hungarian) in torch: is there any point here?

I have a very large assignment problem which takes quite some time on a CPU. I was solving this with the Munkres algorithm in numpy using this scipy code.

I wonder if this is the type of computation which would be greatly sped up by GPU? I would be interested in implementing this code in torch if this would help me. Any thoughts are appreciated, thanks.

1 Like

I found a implementation for solving LAP problem by torch on github, but it is not quiet usable.

I would really appreciate it if someone would share a robust implementation for LAP problem

Can you share the difficulties you are facing with the above code? Do you want to use the auction algorithm for solving LAP problem?. I can work around a solution if you want.

I am trying to get the best combination of two set of word embeddings. So I basically calculate a similar matrix a[i,j] = similarity(Ei, Ej) and then apply a LAP algorithm.

So it looks like:

sim_matrix = torch.zeros([100, 100], dtype=torch.float)
nn.init.uniform_(sim_matrix)
auction_lap(sim_matrix)

and I got this error:

Traceback (most recent call last):
  File "E:/ζ–‡ζ‘£/code/EAbyRule/graph_completion/auction_lap.py", line 67, in <module>
    auction_lap(a)
  File "E:/ζ–‡ζ‘£/code/EAbyRule/graph_completion/auction_lap.py", line 41, in auction_lap
    src=bid_increments.view(-1, 1)
RuntimeError: Dimension out of range (expected to be in range of [-1, 0], but got 1)

This is a fast version of LAP for numpy.


transfer torch 2 numpy and come back!
enjoy it.
1 Like

Try adding

if len(bids_.shape) < 2:
            bids_ = bids_.unsqueeze(dim=0)

between lines 50 and 51 in auction_lap.py:

bids_.zero_()
if len(bids_.shape) < 2:
            bids_ = bids_.unsqueeze(dim=0)
bids_.scatter_(
            dim=1,
            index=first_idx.contiguous().view(-1, 1),
            src=bid_increments.view(-1, 1)
        )

edit:

You will also want make the following adjustment at line 40:

unassigned = (curr_ass == -1).nonzero().squeeze()
if len(unassigned.shape) < 1:
            unassigned = unassigned.unsqueeze(0)
value = X[unassigned] - cost
1 Like

does this not kill the computational graph. could one still calculate losses after converting the tensors to numpy?

when the original scipy method outputs the col and rows indices, this method output only one array indices. could this still link to the original one?
thx

@yuri . Yes, It will disconnect the computational graph. I just mentioned it as a fast solution. for End-to-End training you should look for a substiution.