How to choose the $k$ points that given a cost matrix with other points, give the minimum sum of distances

Question

For two sets of $n$ dimensional points this is their distance matrix:

	$p_{11}$	$p_{12}$	$p_{13}$
$p_{21}$	1	2	3
$p_{22}$	2	5	3
$p_{23}$	2	3	1
$p_{24}$	2	1	8

How can I get the $n$ points of $p_{1i}$ that give the minimum sum of distances in the most efficient way possible.

So far best I could do was apply the Hungarian assignment algorithm in a loop for all possible teams (this takes $\binom{i}{n}$ loops though and is not very efficient)

The solution for n=2 would follow this procedure: find the minimum sum of the minimum distances that each couple of p1,i gives for each row, for example:

$(p_{1,1}, p_{1,2}) = 1^{*}+2+2+1 = 6$

$(p_{1,2}, p_{1,3}) = 2+3+1+1 = 7$

$(p_{1,1}, p_{1,3}) = 1+2+1+2 = 6$

So the optimal couple would be either $(p_{1,1}, p_{1,2})$ or $(p_{1,1}, p_{1,3})$

explanation of the $1^{*}$: its the $min(d(p_{2,1},p_{1,1}), d(p_{2,1},p_{1,2}))=1$

Answer 1

Let $L=\{1,2,3\}$ and $R=\{1,2,3,4\}$ be the left and right sides of the bipartite graph. Let $c_{i,j}$ be the cost of assigning left node $i$ to right node $j$ (the transpose of your table above). Let binary decision variable $x_{i,j}$ indicate whether left node $i$ is assigned to right node $j$, and let binary decision variable $y_i$ indicate whether left node $i$ is selected. The problem is to minimize $$\sum_{i \in L} \sum_{j \in R} c_{i,j} x_{i,j}$$ subject to \begin{align} \sum_{i \in L} x_{i,j} &= 1 &&\text{for $j\in R$} \tag1 \\ \sum_{i \in L} y_i &= k \tag2 \\ x_{i,j} &\le y_i &&\text{for $i \in L$ and $j \in R$} \tag3 \\ \end{align} Constraint $(1)$ assigns exactly one left node per right node. Constraint $(2)$ selects exactly $k$ left nodes. Constraint $(3)$ enforces the logical implication $x_{i,j} \implies y_i$.

Your first optimal solution above has $x_{1,1}=x_{1,2}=x_{1,3}=x_{2,4}=y_1=y_2=1$ and all other variables $0$.