The Hungarian algorithm
Studying this course? Keep your progress in one place.
Key facts
- An allocation problem matches workers to tasks at least total cost.
- Reduce every row, then every column. Rows first.
- Cover the zeros with the fewest lines. If fewer than , augment and cover again.
- The cost of the allocation is always read from the original matrix.
- Square the matrix with a dummy, use for impossible pairings, and subtract from the largest entry to maximise.
Allocation problems
Match workers one-to-one with tasks for the least total cost, using the Hungarian algorithm.
In an allocation (assignment) problem, workers are matched one-to-one with tasks. The cost matrix has entry for worker doing task .
Checking all allocations is hopeless for large , so use the Hungarian algorithm.
It works because subtracting the same number from every entry in a row, or in a column, changes every complete allocation's cost by the same amount, so the best allocation is unchanged.
- 1
Reduce rows
subtract each row minimum
- 2
Reduce columns
subtract each column minimum
- 3
Cover the zeros
fewest horizontal or vertical lines
- 4
Test
n lines? If not, augment and cover again
- 5
Allocate
choose zeros, then add the original costs
How many complete allocations are there for 5 workers and 5 tasks?
Reducing the matrix
Subtract each row's smallest entry from that row, then each column's smallest entry from that column. Always do rows first.
Step 1: reduce the rows. Subtract the smallest entry in each row from every entry in that row, so each row has a zero.
Step 2: reduce the columns. Subtract the smallest entry in each column from that column. A column that already has a zero is unchanged.
Always do rows first.
- 1
Original rows
8, 12, 8 / 10, 7, 11 / 12, 3, 9
- 2
Subtract row minima
Minima are 8, 7 and 3
- 3
Rows reduced
0, 4, 0 / 3, 0, 4 / 9, 0, 6
- 4
Then the columns
Subtract each column minimum; a column with a zero is unchanged
| Original | Rows reduced | |
|---|---|---|
| Row 1 | 8, 12, 8 | 0, 4, 0 |
| Row 2 | 10, 7, 11 | 3, 0, 4 |
| Row 3 | 12, 3, 9 | 9, 0, 6 |
Original
- Row 1:
- 8, 12, 8
- Row 2:
- 10, 7, 11
- Row 3:
- 12, 3, 9
Rows reduced
- Row 1:
- 0, 4, 0
- Row 2:
- 3, 0, 4
- Row 3:
- 9, 0, 6
Worked example
Reduce the matrix .
- 1
Row minima are 8, 7 and 3.
- 2
Subtract them to give .
- 3
Every column already contains a zero, so column reduction changes nothing.
A row is . What is it after row reduction?
Covering and augmenting
Augment: subtract the smallest uncovered entry from uncovered entries and add it where two lines cross. Then cover again.
Step 3: test. Draw the minimum number of straight lines (horizontal or vertical) covering every zero. If there are lines, a complete allocation of zeros exists: go to step 5.
Step 4: augment. If fewer than lines are needed, find the smallest uncovered entry. Subtract it from every uncovered entry and add it to every entry covered twice (where lines cross). Entries covered once are unchanged. Return to step 3.
Step 5: allocate. Choose zeros one per row and column, starting with a row or column with a single zero. Add the costs from the original matrix.
- 1
Cover the zeros
Fewer than 3 lines are needed, so the matrix is not ready
- 2
Smallest uncovered entry
It is 3
- 3
Augment
Subtract 3 from uncovered entries; add 3 where two lines cross
- 4
Result
0, 7, 0 / 0, 0, 1 / 6, 0, 3; cover again
| Before augmenting | After augmenting | |
|---|---|---|
| Row 1 | 0, 4, 0 | 0, 7, 0 |
| Row 2 | 3, 0, 4 | 0, 0, 1 |
| Row 3 | 9, 0, 6 | 6, 0, 3 |
Before augmenting
- Row 1:
- 0, 4, 0
- Row 2:
- 3, 0, 4
- Row 3:
- 9, 0, 6
After augmenting
- Row 1:
- 0, 7, 0
- Row 2:
- 0, 0, 1
- Row 3:
- 6, 0, 3
Worked example
Continue from the reduced matrix for Ana, Ben and Cleo (rows) and tasks 1 to 3 (columns). The original matrix was .
- 1
Row 1 and column 2 cover all the zeros: 2 lines, and , so augment.
- 2
The smallest uncovered entry is 3.
- 3
Subtract 3 from uncovered entries and add 3 at the crossing (row 1, column 2).
- 4
Now three lines are needed. Cleo has one zero, in column 2, so Cleo takes task 2; Ben then takes task 1 and Ana task 3.
- 5
Cost from the original matrix: .
After covering the zeros of a 4 by 4 matrix you need 3 lines. What next?
Dummy locations
The matrix must be square. Add a dummy task or worker filled with equal values, normally 0.
The algorithm needs a square matrix. With more workers than tasks (or the reverse), add a dummy task (or worker).
Fill the dummy row or column with the same value, normally 0, so it favours no one. Whoever is matched with the dummy does no task, and the dummy adds nothing to the cost.
Example: four drivers and three deliveries. Add a dummy delivery costing 0 for every driver. Row reduction then changes nothing, because every row already has a zero.
- 1
Check the size
For example 4 drivers and 3 deliveries is not square
- 2
Add a dummy
A fourth delivery, as a new column
- 3
Fill with equal values
Normally 0, so it favours no one
- 4
Apply the algorithm
Whoever is matched with the dummy does no task
| More workers | More tasks | |
|---|---|---|
| Add | a dummy task (a column) | a dummy worker (a row) |
| Fill with | 0 | 0 |
More workers
- Add:
- a dummy task (a column)
- Fill with:
- 0
More tasks
- Add:
- a dummy worker (a row)
- Fill with:
- 0
There are 5 workers and 3 tasks. What do you add?
Incomplete data and maximising
Put a very large in a forbidden cell. To maximise, subtract every entry from the largest, then apply the algorithm.
If a worker cannot do a task, put a very large number in that cell. It can never appear in the least-cost allocation, but you can still apply the algorithm. Treat symbolically: write , not a number.
To maximise profit, subtract every entry from the largest entry of the original matrix and apply the algorithm to the new matrix. Read the profit from the original.
If the largest profit is 14, a profit of 5 becomes 9 and 14 becomes 0. For a converted minimum of 9 means a maximum profit of .
- 1
Impossible pairing
Put a very large M in that cell
- 2
Maximising
Subtract every entry from the largest entry
- 3
Run the algorithm
Treat M symbolically, such as M − 23
- 4
Read the answer
Take the cost or profit from the original matrix
| Impossible pairing | Maximise profit | |
|---|---|---|
| Step 1 | Put a very large in the cell | Subtract every entry from the largest |
| Step 2 | Run the algorithm as normal | Read the profit from the original |
Impossible pairing
- Step 1:
- Put a very large in the cell
- Step 2:
- Run the algorithm as normal
Maximise profit
- Step 1:
- Subtract every entry from the largest
- Step 2:
- Read the profit from the original
The largest profit in a matrix is 20. What does a profit of 12 become?
Try an exam question
Use the Hungarian algorithm on the cost matrix to find the least-cost allocation of three workers to three tasks, and its cost.
[4 marks]
- [1]Reduces rows (subtract 5, 4, 6), then column 1 (subtract 2), giving .
- [1]Two lines cover the zeros, which is fewer than 3, so augments.
- [1]Subtracts the smallest uncovered entry 2 from uncovered entries and adds it at the crossing.
- [1]Allocates worker 2 to task 3 and the others to tasks 1 and 2, with total cost 19 from the original matrix.
That's the notes covered.
Carry on to the next subtopic.
Try a question
The rows are reduced first. What is the entry for Ben doing task W in the row-reduced matrix?
1 mark, marked against the mark scheme
The rows are reduced first. What is the entry for Ben doing task W in the row-reduced matrix?
1 mark, marked against the mark scheme