The Hungarian algorithm

The Hungarian algorithm

Spec 2.1 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • An allocation problem matches nn workers to nn tasks at least total cost.
  • Reduce every row, then every column. Rows first.
  • Cover the zeros with the fewest lines. If fewer than nn, augment and cover again.
  • The cost of the allocation is always read from the original matrix.
  • Square the matrix with a dummy, use MM for impossible pairings, and subtract from the largest entry to maximise.

Allocation problems

Match nn workers one-to-one with nn tasks for the least total cost, using the Hungarian algorithm.

In an allocation (assignment) problem, nn workers are matched one-to-one with nn tasks. The cost matrix has entry cijc_{ij} for worker ii doing task jj.

Checking all n!n! allocations is hopeless for large nn, 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. 1

    Reduce rows

    subtract each row minimum

  2. 2

    Reduce columns

    subtract each column minimum

  3. 3

    Cover the zeros

    fewest horizontal or vertical lines

  4. 4

    Test

    n lines? If not, augment and cover again

  5. 5

    Allocate

    choose zeros, then add the original costs

The Hungarian algorithm

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. 1

    Original rows

    8, 12, 8 / 10, 7, 11 / 12, 3, 9

  2. 2

    Subtract row minima

    Minima are 8, 7 and 3

  3. 3

    Rows reduced

    0, 4, 0 / 3, 0, 4 / 9, 0, 6

  4. 4

    Then the columns

    Subtract each column minimum; a column with a zero is unchanged

Reducing the matrix (rows 8 12 8 / 10 7 11 / 12 3 9), rows first.

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 (8128107111239)\begin{pmatrix}8&12&8\\10&7&11\\12&3&9\end{pmatrix}.

A row is (5,9,7)(5, 9, 7). 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 nn lines, a complete allocation of zeros exists: go to step 5.

Step 4: augment. If fewer than nn 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. 1

    Cover the zeros

    Fewer than 3 lines are needed, so the matrix is not ready

  2. 2

    Smallest uncovered entry

    It is 3

  3. 3

    Augment

    Subtract 3 from uncovered entries; add 3 where two lines cross

  4. 4

    Result

    0, 7, 0 / 0, 0, 1 / 6, 0, 3; cover again

Augmenting the reduced matrix 0 4 0 / 3 0 4 / 9 0 6.

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 (8128107111239)\begin{pmatrix}8&12&8\\10&7&11\\12&3&9\end{pmatrix}.

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. 1

    Check the size

    For example 4 drivers and 3 deliveries is not square

  2. 2

    Add a dummy

    A fourth delivery, as a new column

  3. 3

    Fill with equal values

    Normally 0, so it favours no one

  4. 4

    Apply the algorithm

    Whoever is matched with the dummy does no task

Making the matrix square with a dummy.

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 MM 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 MM in that cell. It can never appear in the least-cost allocation, but you can still apply the algorithm. Treat MM symbolically: write M−23M-23, 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 n=3n=3 a converted minimum of 9 means a maximum profit of 42−9=3342-9=33.

  1. 1

    Impossible pairing

    Put a very large M in that cell

  2. 2

    Maximising

    Subtract every entry from the largest entry

  3. 3

    Run the algorithm

    Treat M symbolically, such as M − 23

  4. 4

    Read the answer

    Take the cost or profit from the original matrix

Two adjustments before running the Hungarian algorithm.

Impossible pairing

Step 1:
Put a very large MM 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 (9586741069)\begin{pmatrix}9&5&8\\6&7&4\\10&6&9\end{pmatrix} to find the least-cost allocation of three workers to three tasks, and its cost.

[4 marks]

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

Revision notes