I have a question that I have been thinking about. Suppose we have $n$ agents, $m$ tasks, a cost matrix with $M_{ij}$ being the cost of agent $i$ performing task $j$, and are given a value $k \leq n$. How can we find the $k$ unique agents, who when each optimally allocated a unique task, result in a minimum total cost? Can this be related to the assignment problem? Thank you very much for any guidance or assistance.
4
-
$\begingroup$ The constraints $m\times n$ arbitrary and $k<n$ don't quite make sense without some additional details. Right now we could choose $k=0$ and solve the problem. $\endgroup$– Matthew CNov 28, 2019 at 0:11
-
$\begingroup$ Thank you for your feedback. I am trying to find a general approach for any $k < n$. As you point out, when $k = 0$, and also when $k=1$ and $k=n$, the approach is trivial. But I am not sure of the approach for other values of $k$. $\endgroup$– user89692Nov 28, 2019 at 0:14
-
$\begingroup$ Here's a greedy heuristic which is kind of slow: For $k=1$, find the smallest element in the matrix. For $k=2$, first find the smallest element in the matrix; then strike out its row and column. Then find the smallest element of the remaining matrix. Similarly for $k$ to min$(n,m)$ (I believe you need a minimum there because if $n>m$, for instance, then you won't be able to make unique assignments) $\endgroup$– Matthew CNov 28, 2019 at 0:41
-
$\begingroup$ (The greedy heurstic won't actually work, for instance with the matrix $[[9,2],[2,1]]$, just putting it out there) $\endgroup$– Matthew CNov 28, 2019 at 0:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
The assignment problem can be extended to solve this problem. The regular problem without the $k$ restriction can be solved by building a Minimum Cost Maximum Flow network is as follow:
We have a source $S$ a sink $T$ and the corresponding bipartite graph in the middle. Note that each edge has two values $f/c$ which denote maximum flow allowed through this edge and cost of each flow unit. Now, the problem is that we want to allow at most $k$ units of flow from $S$ to $T$. To do this, just duplicate node $S$ into $S_1$ and $S_2$ and put an edge among them such that cost of each unit is 0 (no penalty) and maximum flow allowed is $k$. The new graph will look like this:
The minimum cost maximum flow from $S_1$ to $T$ is the solution to the original problem for a fixed $k$.
-
$\begingroup$ Thank you very much for this thorough and detailed answer. I tried this out and it is painfully slow using some of the best packages for even a small cost matrix. Do you know if it is possible to frame the problem into the standard assignment problem framework? This would allow the application of fast AP solvers. Alternatively, would you know of a relaxation, approximation, or heuristic that would permit this framing? Thank you very much. $\endgroup$ Nov 30, 2019 at 0:33
-
$\begingroup$ What makes you think the solution for the min cost flow here would be an integer flow solution? $\endgroup$ May 2, 2020 at 0:06
-
1