mathematics//optimization//combinatorial optimization//assignment problem
The assignment problem is the combinatorial problem of matching \(n\) agents to \(n\) tasks one to one so that the total cost is minimal, given a cost for every agent-task pair; it is how a warehouse gives orders to robots, a dispatcher sends drones to hot spots and a tracker pairs radar echoes with existing tracks. What goes in is the cost matrix \(c_{ij}\) (the travel time of robot \(i\) to shelf \(j\), the distance between track \(i\) and echo \(j\)); what comes out is the matching.
The assignment problem is the combinatorial problem of matching nnn agents to nnn tasks one to one so that the total cost is minimal, given a cost for every agent-task pair; it is how a warehouse gives orders to robots, a dispatcher sends drones to hot spots and a tracker pairs radar echoes with existing tracks. What goes in is the cost matrix cijc_{ij}cij (the travel time of robot iii to shelf jjj, the distance between track iii and echo jjj); what comes out is the matching.
minx ∑i,jcij xijwith∑jxij=1, ∑ixij=1, xij∈{0,1}\min_{x}\; \sum_{i,j} c_{ij}\,x_{ij}\quad\text{with}\quad \sum_{j} x_{ij}=1,\;\; \sum_{i} x_{ij}=1,\;\; x_{ij}\in\{0,1\}xmini,j∑cijxijwithj∑xij=1,i∑xij=1,xij∈{0,1}
Here xijx_{ij}xij is 1 when agent iii takes task jjj; the two sums say that each agent does one task and each task is done by one agent. The obvious rule, giving each agent the cheapest task still free, fails on the smallest case. With costs (122100)\left(\begin{smallmatrix}1&2\2&100\end{smallmatrix}\right)(122100), greedy takes the 1 and leaves the second agent with the 100, a total of 101, while crossing over costs 2+2=42+2=42+2=4: the first choice condemned the other agent. Despite its n!n!n! candidates the problem is easy, solved exactly in O(n3)O(n^3)O(n3), and SciPy's linear_sum_assignment handles a 1000 by 1000 matrix in under a second on a laptop, rectangular matrices included.
expected, greedy2.90 expected, optimal2.90 expected, in rounds3.17 6 agents, 4 tasks, dispersion 0.60: the greedy plan completes 2.90 tasks on average, the optimal assignment 2.90 (spare agents sent in a second pass), and assigning in rounds, reassigning agents only to the tasks that failed, 3.17.
Here the matrix holds success probabilities and the methods maximize expected tasks done. Keep the spread of probabilities low and greedy ties the optimum; raise it and watch the gap grow, then give more agents than tasks and switch to In rounds, which reassigns after seeing which tasks failed.
Two solvers cover practice. The Hungarian algorithm needs the whole matrix in one place and is the default on a server; the auction algorithm lets agents reach the same matching by bidding over a radio link with no centre.
Variants are handled in the matrix. A forbidden pair gets a very large cost, a benefit becomes a cost by changing its sign (or with maximize=True), and a surplus of agents leaves some unassigned. When an agent does several tasks in sequence the problem becomes the bundle allocation of task allocation, and when several agents may go to one target with probabilities of success it becomes weapon-target assignment, a far harder problem.
The optimum of a matrix is only as good as its costs. Travel times change while robots move, so reassigning every few seconds with fresh costs beats the perfect assignment of ten minutes ago, and when all costs are similar the nearest free robot is almost as good; the figure's thousand simulated runs are the way to measure that gap before choosing.