Assignment Models

An assignment problem pairs $n$ agents with $n$ tasks, one each, at the lowest total cost. Checking every possibility means $n!$ combinations — over three million for ten workers — so a systematic method is essential.

The assignment problem

The data is an $n \times n$ cost matrix: entry $(i,j)$ is the cost of giving task $j$ to agent $i$.

Each agent takes exactly one task and each task goes to exactly one agent. With three workers there are $3! = 6$ possibilities, which could be listed — but with ten there are $3\,628\,800$.

The Hungarian algorithm

Step 1 — row reduction. Subtract the smallest entry in each row from every entry in that row. Each row now contains at least one zero.

Step 2 — column reduction. Do the same for each column.

Step 3 — cover the zeros. Find the minimum number of horizontal and vertical lines that cover every zero.

• If that number equals $n$, an optimal assignment exists among the zeros — go to step 5.
• If it is less than $n$, continue to step 4.

Step 4 — adjust. Find the smallest uncovered entry. Subtract it from every uncovered entry, and add it to every entry covered twice (at a line intersection). Leave singly-covered entries alone. Return to step 3.

Step 5 — assign. Choose zeros so that each row and each column is used exactly once. Start with any row or column containing a single zero — that assignment is forced.

A worked assignment

Row reduction. The row minima are 2, 3 and 1:

$$\begin{pmatrix} 7 & 0 & 5 \\ 3 & 1 & 0 \\ 4 & 7 & 0 \end{pmatrix}$$

Column reduction. The column minima are now 3, 0 and 0:

$$\begin{pmatrix} 4 & 0 & 5 \\ 0 & 1 & 0 \\ 1 & 7 & 0 \end{pmatrix}$$

Cover the zeros. Column 2 covers the zero in row 1; row 2 covers its two zeros; column 3 covers the zero in row 3. That is 3 lines, and $n = 3$ — so an optimal assignment is available.

Assign. Row 1 has a single zero, in column 2, so $W_1 \to J_2$. Row 3 has a single zero, in column 3, so $W_3 \to J_3$. That leaves $W_2 \to J_1$.

Read the costs from the original matrix:

$$2 + 6 + 1 = 9$$

Checking all six possibilities confirms 9 is the minimum — the next best is 10.

Maximisation problems

The algorithm minimises. To maximise a profit or score matrix, convert it first:

Subtract every entry from the largest entry in the whole matrix, then minimise the result.

The largest profits become the smallest costs, so minimising the new matrix maximises the original. The assignment found is the answer; the total is read, once again, from the original matrix.

Unbalanced problems

The algorithm needs a square matrix. If there are more tasks than agents (or the reverse), add a dummy row or column filled with zeros.

Five jobs and four workers, for example, need a dummy fifth worker whose costs are all zero. The job assigned to that dummy is the one left undone — and because its costs are zero, it never affects the total.

Interpreting the solution

An exam answer needs three things:

1. The pairing, in words: "$W_1$ does $J_2$, $W_2$ does $J_1$, $W_3$ does $J_3$."
2. The total, computed from the original matrix: "total cost 9".
3. Any unassigned agent or task, where a dummy was used.