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

1

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
2

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

3

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.

4

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)
5

This is a fast version of LAP for numpy.


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

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
8

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

9

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

10

@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.

11

Here is a CUDA implementation for the batched linear assignment. It uses data parallelism and is useful for a large set of small problems.