The Assignment Problem
Four machines, four jobs, and a table of costs for every pairing — assign each job to exactly one machine so the total cost is least. This is the assignment problem, the tidiest member of the network family: a transportation problem where every supply and demand equals one. That extreme simplicity would cripple the ordinary transportation method with degeneracy, so the assignment problem gets its own beautifully direct algorithm — the Hungarian method — which solves it with nothing more than subtraction and a clever counting of lines.
- The assignment problem and its one-to-one matching structure.
- The 0–1 integer formulation and why the LP relaxation still gives integer answers.
- How assignment is a special transportation problem — and why it needs its own method.
- The Hungarian method: reduce, cover, adjust, assign.
- Handling unbalanced problems, maximization, and prohibited assignments.
- The line-covering optimality test and how to read off the assignment.
The Assignment Problem
In the assignment problem, \(n\) agents must be matched to \(n\) tasks so that each agent does exactly one task and each task is done by exactly one agent, at minimum total cost. The data are an \(n \times n\) cost matrix \([c_{ij}]\), where \(c_{ij}\) is the cost of agent \(i\) doing task \(j\). The answer is a one-to-one matching — a permutation — and there are \(n!\) of them, far too many to enumerate for even modest \(n\).
Formulation and Structure
Let \(x_{ij} = 1\) if agent \(i\) is assigned to task \(j\), and \(0\) otherwise. Each agent takes one task (row sums \(=1\)) and each task gets one agent (column sums \(=1\)):
The constraint matrix is totally unimodular, so the LP relaxation automatically produces integer (0–1) optimal solutions — no branch-and-bound needed. This is exactly why a simple combinatorial algorithm can solve the problem exactly, and it is the same property that makes transportation solutions integer.
Relation to Transportation
An assignment problem is a transportation problem in which every supply and every demand equals \(1\): each agent "supplies" one unit of work, each task "demands" one unit. We could solve it with the MODI method of Chapter 12 — but we should not. With all supplies and demands equal to \(1\), a basic feasible solution needs \(m + n - 1 = 2n - 1\) occupied cells, yet a real assignment uses only \(n\) of them. Every basic solution is therefore heavily degenerate, forcing many \(\varepsilon\)-fillers and painful bookkeeping.
The Hungarian Method
The Hungarian method rests on a simple fact: adding or subtracting a constant from an entire row or column of the cost matrix changes every complete assignment's total by the same amount, so it never changes which assignment is optimal. We exploit this to create zeros, then seek an assignment made entirely of zeros.
The five steps: (1) subtract each row's minimum from that row; (2) subtract each column's minimum from that column; (3) cover all zeros with the fewest possible horizontal/vertical lines; (4) if the number of lines is less than \(n\), find the smallest uncovered entry, subtract it from all uncovered entries and add it to entries covered twice, then re-cover; (5) once the minimum number of lines equals \(n\), a complete zero-assignment exists — read it off.
A Worked Solution
Assign three workers to three jobs with this cost matrix:
| J₁ | J₂ | J₃ | |
|---|---|---|---|
| W₁ | 4 | 2 | 8 |
| W₂ | 4 | 3 | 7 |
| W₃ | 3 | 1 | 6 |
Row reduction (subtract \(2, 3, 1\)) then column reduction (subtract column minima \(1, 0, 4\)) gives:
| J₁ | J₂ | J₃ | |
|---|---|---|---|
| W₁ | 1 | 0 | 2 |
| W₂ | 0 | 0 | 0 |
| W₃ | 1 | 0 | 1 |
Cover the zeros: row 2 and column 2 cover every zero — just 2 lines, fewer than \(n = 3\), so this is not yet optimal.
Adjust: the smallest uncovered entry is \(1\). Subtract it from all uncovered entries and add it to the doubly-covered entry \((W_2, J_2)\). Re-covering now needs \(3\) lines \(= n\), and a complete zero-assignment appears:
| J₁ | J₂ | J₃ | |
|---|---|---|---|
| W₁ | 0 | 0 | 1 |
| W₂ | 0 | 1 | 0 |
| W₃ | 0 | 0 | 0 |
Reading the highlighted zeros back into the original matrix gives total cost \(12\) — the minimum over all \(3! = 6\) possible assignments, obtained without enumerating any of them.
Unbalanced, Maximization & Special Cases
Three variations cover almost every real assignment problem, each reduced to the standard form before running the Hungarian method:
| Situation | Fix before solving |
|---|---|
| Unbalanced (agents \(\ne\) tasks) | Add dummy rows or columns of zero cost to square the matrix |
| Maximization (profits, not costs) | Subtract every entry from the largest entry (or negate) to get an equivalent minimization |
| Prohibited assignment | Put a very large cost \(M\) in the forbidden cell so it is never chosen |
Once squared and cast as a minimization with any forbidden cells blocked by \(M\), the Hungarian method proceeds unchanged. A dummy agent assigned to a task simply means that task goes undone (or that machine sits idle); a dummy task assigned to an agent means that agent is unused.
Optimality & Making Assignments
The stopping test is a theorem in disguise. By König's theorem, the minimum number of lines needed to cover all zeros equals the maximum number of independent zeros (zeros with no two in the same row or column). A complete assignment needs \(n\) independent zeros, so:
To read off the assignment, start with any row or column that has a single zero, assign it, cross out that row and column, and repeat. When every row has exactly one assigned zero, you have the optimal permutation. If a choice arises (multiple zeros), any valid completion gives the same optimal cost.
Worked Examples
Problem. Formulate the assignment of 3 agents to 3 tasks as a 0–1 program.
Solution. With \(x_{ij} \in \{0,1\}\): \(\min \sum_{i}\sum_{j} c_{ij}x_{ij}\) subject to \(\sum_j x_{ij} = 1\) for each agent \(i\) and \(\sum_i x_{ij} = 1\) for each task \(j\). Because the matrix is totally unimodular, replacing \(x_{ij} \in \{0,1\}\) with \(x_{ij} \ge 0\) yields the same optimum — the LP is guaranteed integer.
Problem. Reduce the matrix \(\begin{smallmatrix}4&2&8\\4&3&7\\3&1&6\end{smallmatrix}\).
Solution. Subtract row minima \(2, 3, 1\): \(\begin{smallmatrix}2&0&6\\1&0&4\\2&0&5\end{smallmatrix}\). Then subtract column minima \(1, 0, 4\): \(\begin{smallmatrix}1&0&2\\0&0&0\\1&0&1\end{smallmatrix}\). Each reduction creates at least one zero in every row and column touched, without changing the optimal assignment.
Problem. For the reduced matrix above, find the minimum number of covering lines and decide whether it is optimal.
Solution. Row 2 (all zeros) and column 2 (all zeros) together cover every zero — \(2\) lines. Since \(2 < n = 3\), no complete zero-assignment exists yet, so the current reduction is not optimal and an adjustment is required.
Problem. Perform the adjustment on that matrix.
Solution. The smallest uncovered entry is \(1\). Subtract \(1\) from all uncovered entries \((W_1J_1, W_1J_3, W_3J_1, W_3J_3)\) and add \(1\) to the doubly-covered \((W_2J_2)\), giving \(\begin{smallmatrix}0&0&1\\0&1&0\\0&0&0\end{smallmatrix}\). Now \(3\) lines are needed and the independent zeros \(W_1J_2,\ W_2J_3,\ W_3J_1\) form a complete assignment of cost \(12\).
Problem. A profit-maximizing assignment has profits \(\begin{smallmatrix}5&9\\8&4\end{smallmatrix}\). Convert to a minimization.
Solution. Subtract every entry from the largest, \(9\): \(\begin{smallmatrix}4&0\\1&5\end{smallmatrix}\). Minimizing this equivalent cost matrix maximizes the original profit. Row/column reduction then gives the zero-assignment \(W_1 \to J_2,\ W_2 \to J_1\) with profit \(9 + 8 = 17\).
Problem. There are 3 machines but only 2 jobs, and machine 2 cannot do job 1. Prepare the matrix.
Solution. Add a dummy job (a zero-cost column) to square the \(3 \times 3\) matrix; the machine assigned to the dummy stays idle. Put a very large cost \(M\) in the \((\text{machine 2}, \text{job 1})\) cell so the Hungarian method never selects that forbidden pairing. Then solve as usual.
Chapter Summary
Match \(n\) agents to \(n\) tasks one-to-one at least total cost.
0–1 program; totally unimodular, so the LP relaxation is integer.
All supplies/demands \(=1\); too degenerate for MODI, so use the Hungarian method.
Reduce rows, reduce columns, cover zeros, adjust, assign.
Minimum covering lines \(= n\) ⇔ complete zero-assignment (König's theorem).
Dummy for unbalanced, subtract-from-max for maximization, \(M\) for prohibited.
Problems
Solve each by the Hungarian method, showing the reduction, covering, and adjustment steps. Difficulty rises down the list.
- Write the 0–1 formulation for a \(4 \times 4\) assignment and state the constraint on each row and column.
- Explain why the assignment problem is a transportation problem, and why MODI is a poor choice for it.
- Perform row and column reduction on \(\begin{smallmatrix}9&11&14\\6&15&13\\12&13&6\end{smallmatrix}\).
- For the reduced matrix in Problem 3, cover the zeros and state whether it is optimal.
- Solve the \(3 \times 3\) problem in Problem 3 completely and give the optimal assignment and cost.
- Convert the maximization matrix \(\begin{smallmatrix}7&5\\6&9\end{smallmatrix}\) to an equivalent minimization and solve.
- A \(3 \times 4\) problem has more tasks than agents. How do you make it square, and what does the dummy represent?
- State König's theorem and explain its role in the Hungarian stopping test.
- In a machine–job problem, machine 3 cannot do job 2. Show how to encode this and why \(M\) works.
- Explain why subtracting a constant from a row cannot change which assignment is optimal.
- After adjustment a matrix still needs only \(n-1\) lines. What do you do next?
- Four technicians must be assigned to four repair jobs with cost matrix \(\begin{smallmatrix}20&25&22&28\\15&18&23&17\\19&17&21&24\\25&23&24&24\end{smallmatrix}\). Solve by the Hungarian method and report the optimal assignment and its total cost.