Minimize sum of distances between mutually disjoint bipartite pair of points

user_13350827 0
Viewed 122

I have a multidimensionnal array which represent distances between two group of points (colored by blue and red respectively).

import numpy as np
distance=np.array([[30,18,51,55],
                   [35,15,50,49],
                   [36,17,40,32],
                   [40,29,29,17]])

Each column represent the red dot and rows are for blue dots. Values in this matrix represent the distance between red and blue dots. Here is a sketch to understand what it looks like:

enter image description here

Question: How to find the minimum of the sum of distances between mutually disjoint (blue, red) pairs?

Attempt

I am expecting to find 1=1, 2=2, 3=3 and 4=4 in the above image. However, if i use a simple argmin numpy function like:

for liste in distance:
    np.argmin(liste)

the result is

1
1
1
3

because the 2 red point is the nearest of 1,2 and 3 blue point.

Is there a way to do something generic in that case to make things better? I mean without using a lot of if statements and a while function.

scipy multidimensional-array numpy arrays python
2 Answers

The problem is known as the assignment problem in operations management and can be solved efficiently by Hungarian Algorithm. In your case, the distance can be viewed as a kind of "cost" function which is going to be minimized in its total.

Luckily, scipy has a nice linear_sum_assignment() (see official docs and example) implemented, so you don't have to reinvent the wheel. The function returns the matched indices.

from scipy.optimize import linear_sum_assignment
distance=np.array([[30,18,51,55],
                   [35,15,50,49],
                   [36,17,40,32],
                   [40,29,29,17]])

row_ind, col_ind = linear_sum_assignment(distance)

# result
col_ind
Out[79]: array([0, 1, 2, 3])
row_ind
Out[80]: array([0, 1, 2, 3])
user_32186930

You can use itertools.permutations to find all possible solutions. Then, you calculate which solution minimize the total pair-wise distance.

import itertools
import numpy as np

distance=np.array([[30,18,51,55],[35,15,50,49],[36,17,40,32],[40,29,29,17]])

permutation=[x for x in itertools.permutations([0,1,2,3],4)]
x_opt=permutation[0]
d_opt=sum([distance[i,x_opt[i]] for i in range(len(distance[0]))])
for x in permutation:
    d=sum([distance[i,x[i]] for i in range(len(distance[0]))])
    if d<d_opt:
        (d_opt,x_opt)=(d,x)
print(x_opt)

The result will be in this case:

(0,1,2,3)
user_142805200
Related