topic badge

7.05 Assignment allocation

Lesson

Introduction

What do these networks have in common?

This image shows 4 networks each with blue and orange vertices. Ask your teacher for more information.

For each network, we have split the vertices into two groups, blue and orange. Notice that the orange vertices are only connected to blue vertices, and the blue vertices are only connected to orange vertices - there are no edges between blue vertices, and no edges between orange ones either.

Whenever we can divide the vertices up like this, we call the network a bipartite graph.

We are going to study these kinds of networks, with one group of vertices representing tasks, and the other representing agents - people, companies, countries, and so on. These are called allocation problems (sometimes assignment problems).

Allocation problems

Let's consider the following situation:

Paula, Rohan and Erin are working together on a group project over the weekend. There are a number of tasks that need to get done, but each student is better at some things and worse at others. This table shows how many hours it would take for them to do each part of the project:

Making the posterWriting the report Writing the speech
\text{Paula}1058
\text{Rohan}6712
\text{Erin}985

Once every task is completed, they get to go home. Who should do what part to make sure they can go home the earliest?

There are two ways we can represent this same information - one is by using a matrix:

\begin{pmatrix} 10 & 5 & 8\\ 6 & 7 & 12 \\ 9 & 8 & 5 \end{pmatrix}

The matrix is just a more condensed version of the table. A more interesting way is to represent the information using a bipartite graph:

This image shows a bipartite graph for how Paula Rohan and Erin could do 3 tasks. Ask your teacher for more information.

This is a bipartite network because every person is connected to one or more tasks, but a person isn’t connected to a person, or a task to a task.

We want to pick out three edges so that each person and task has exactly one edge coming out of it, forming an allocation. Here are two ways we could do it:

This image shows 2 bipartite graphs with highlighted edges. Ask your teacher for more information.

In the first allocation, the group has to stay for 12 hours, since Rohan takes 12 hours to do the speech while Paula and Erin wait around. The second allocation is a little better since the group stays for 8 hours and, in this allocation, it’s Rohan who does the waiting.

With some further investigation, we would find that this is the best allocation possible:

This image shows a bipartite graph with highlighted edges. Ask your teacher for more information.

This allocation has the group only taking 6 hours to complete the project, half the time of the first allocation we tried. It is the optimum allocation.

We may have spotted this allocation straight away just by looking at the table. It allocates everyone the task that they’re best at. But this isn’t always the case, so be sure to check thoroughly.

Examples

Example 1

Three people, Elise, Poppy and Richard, are each to be given 1 task (T1, T2, or T3) to complete on their own.

Each person is able to complete the 3 tasks that are available in a set time. These times, in minutes, are shown in the network diagram below.

This image shows a bipartite graph with 6 vertices. Ask your teacher for more information.

Represent this data in a matrix.

\quad\begin{matrix} T1 & T2 & T3 \end{matrix} \\ \begin{matrix} E \\ P \\ R \\ \end{matrix} \begin{bmatrix} & ⬚ & ⬚ & ⬚ &\\ & ⬚ & ⬚ & ⬚ &\\ & ⬚ & ⬚ & ⬚ &\\ \end{bmatrix}

Worked Solution
Create a strategy

Enter the weights of the edge that connect the person in each row to the task in each column.

Apply the idea

Vertex E is connected to T1 by the edge with weight 27. It is also connected to T2 by the edge with weight 54, and to T3 by the edge with weight 44. So we get the following first row of the matrix: \quad\begin{matrix} T1 & T2 & T3 \end{matrix} \\ \begin{matrix} E \\ P \\ R \\ \end{matrix} \begin{bmatrix} & 27 & 54 & 44 &\\ & ⬚ & ⬚ & ⬚ &\\ & ⬚ & ⬚ & ⬚ &\\ \end{bmatrix}

Repeating the same process for P and R will complete the matrix:

\quad\begin{matrix} T1 & T2 & T3 \end{matrix} \\ \begin{matrix} E \\ P \\ R \\ \end{matrix} \begin{bmatrix} & 27 & 54 & 44 &\\ & 11 & 50 & 33 &\\ & 17 & 55 & 51 &\\ \end{bmatrix}

Example 2

Consider the following bipartite graph.

This image shows a bipartite graph. Ask your teacher for more information.

Which of the following allocations agree with the bipartite graph?

A
First column lists A, B, C, D, and E. Second column lists 1, 4, 2, 3, and 5.
B
First column lists A, B, C, D, and E. Second column lists 3, 1, 5, 2, and 4.
C
First column lists A, B, C, D, and E. Second column lists 3, 5, 2, 1, and 4.
D
First column lists A, B, C, D, and E. Second column lists 1, 3, 5, 2, and 4.
Worked Solution
Create a strategy

Choose the options where the corresponding connected vertices match the given graph.

Apply the idea

Option A shows C and 2 are connected which is not true in the graph.

Option C shows B and 5 are connected which is not true in the graph.

Option D shows B and 3 are connected which is not true in the graph.

Option B has connections that are included in the graph. The answer is option B.

Idea summary

Bipartite graphs are networks to represent allocation problems.

Allocation problems require connecting agents to one or more tasks, preferably with the lowest weights.

Hungarian algorithm - graph version

As we just saw, we can represent allocation problems using graphs, tables and matrices. With our example above there were 3 agents and 3 tasks and while we could spot the optimal solution by observation this may not always be clear. If the solution was not obvious with a case of 3 agents and 3 tasks we could enumerate all possible assignments and find the minimum. There are 6 possible assignments when the number of agents and tasks is 3, so enumerating all possibilities would not be too onerous.

However, for the general case of n agents and n jobs there are n! possibilities to check, which quickly becomes too large to check practically. For n=4 there are 24 possibilities, n=5 there are 120 possibilities. We can see that we need a method to find the optimal solution more effectively. The Hungarian Algorithm gives one such method.

The Hungarian algorithm was invented by Harold Kuhn in 1955. He relied heavily on earlier work done by two Hungarian mathematicians, Jeno Egerváry and Dénes Konig, so he named it after them.

We will first apply the Hungarian algorithm with a graphical procedure to a simple problem. For more complex examples it is easier to use a matrix based procedure that is described later in this lesson.

These steps can be used to solve simple assignment problems using the graphical procedure:

  1. Subtract the lowest weight of edges coming out of each vertex on the left from the others.

  2. Subtract the lowest weight of edges coming out of each vertex on the right from the others.

  3. Make a valid assignment using the edges of weight zero.

  4. Relate the zeros back to the data in the original matrix to answer the question in context.

If after step 2 you cannot make a valid assignment then using the matrix version of this algorithm would be recommended. It is generally easier to keep track of the changes required at this stage.

Examples

Example 3

Harvey, Kiara, and Dao are on the medical support team for a company that runs events. There are events at three major cities this weekend, and the cost for each of them to travel to each city is given in the table below:

SydneyMelbournePerth
\text{Harvey}\$200\$250\$320
\text{Kiara}\$280\$300\$250
\text{Dao}\$300\$470\$510

Which allocation costs the least money overall?

Worked Solution
Create a strategy

Draw a graph for the table and subtract the lowest weight of edges coming out of each vertex on the left and right.

Apply the idea

We can draw the information in the table in the following graph:

This image shows a bipartite graph of trip costs. Ask your teacher for more information.

The first step of the algorithm is to subtract the lowest weight of edges coming out of each vertex on the left from the others.

This image shows bipartite graphs highlighting Harvey's cost of trip. Ask your teacher for more information.

The lowest weight from the Harvey vertex is 200, so we subtract this from all the other edges coming out of the Harvey vertex.

This image shows bipartite graphs highlighting Kiara's cost of trip. Ask your teacher for more information.

The lowest weight from the Kiara vertex is 250, so we subtract this from all the other edges coming out of the Kiara vertex.

This image shows bipartite graphs highlighting Dao's cost of trip. Ask your teacher for more information.

The lowest weight from the Dao vertex is 300, so we subtract this from all the other edges coming out of the Dao vertex.

Each person now has a 0-edge, but these edges do not all point to different destinations - both Harvey and Dao have a 0-edge to Sydney, and nobody has a 0-edge to Melbourne.

The second step of the algorithm is to subtract the lowest weight of edges coming out of each vertex on the right from the others.

The lowest weight coming out of the Sydney vertex is 0, and since subtracting 0, doesn’t change the network we do nothing. This is the same for Perth.

The cheapest trip to Melbourne is \$50, so we subtract \$50 from all Melbourne trips:

This image shows bipartite graphs highlighting cost of trip to Melbourne. Ask your teacher for more information.

Now there are 0-edges both to and from each person and task. We are ready to do the allocation. There’s only one 0-edge from Perth, and only one from Dao, so we highlight those:

This image shows a bipartite graph highlighting some edges. Ask your teacher for more information.

This leaves Harvey to be connected to Melbourne:

This image shows a bipartite graph highlighting some edges. Ask your teacher for more information.

This is the optimum allocation. If we recover the original edge weights, we can calculate the cost:

This image shows a bipartite graph highlighting some edges and weights. Ask your teacher for more information.

The total, cheapest cost is \$250+\$300+\$250=\$800.

Reflect and check

Interestingly, this involves paying the most to send someone to Sydney. This procedure finds what’s best for the group, not always the individual.

Idea summary

These steps can be used to solve simple assignment problems using the graphical procedure:

  1. Subtract the lowest weight of edges coming out of each vertex on the left from the others.

  2. Subtract the lowest weight of edges coming out of each vertex on the right from the others.

  3. Make a valid assignment using the edges of weight zero.

  4. Relate the zeros back to the data in the original matrix to answer the question in context.

Hungarian algorithm - matrix version

In the previous example, we learned how to find the optimum allocation for a network represented as a graph.

Now we will learn a different way to find the optimum allocation from within the table itself, without ever drawing a bipartite network. This can be very useful when there would be a lot of vertices and edges since the network can get very crowded.

In these examples, we will also look at some small variations to the algorithm to deal with situations where the number of tasks and resources is not the same, and where we want to find the maximum values for our optimum allocation.

Hungarian algorithm minimisation (from a matrix):

  1. Subtract the lowest number in each row from every number in that row.

  2. Subtract the lowest number in each column from every number in that column.

  3. Cover the 0’s with the minimum number of lines. If the number of lines required is less than the total number of rows (or columns), subtract the smallest uncovered value in the matrix from all other uncovered values, and add this value to any number covered by two lines. Repeat this step as many times as required.

  4. Make a valid assignment using the zeros in the matrix.

  5. Relate the zeros back to the data in the original matrix to answer the question in context.

Hungarian algorithm maximisation (from a matrix):

  • Find the maximum value in the matrix and subtract each element in the matrix from this maximum value.

  • Now complete the algorithm with the minimisation procedure:

    1. Subtract the lowest number in each row from every number in that row.

    2. Subtract the lowest number in each column from every number in that column.

    3. Cover the 0’s with the minimum number of lines. If the number of lines required is less than the total number of rows (or columns), subtract the smallest uncovered value in the matrix from all other uncovered values, and add this value to any number covered by two lines. Repeat this step as many times as required.

    4. Make a valid assignment using the zeros in the matrix.

    5. Relate the zeros back to the data in the original matrix to answer the question in context.

Examples

Example 4

A limousine company has to dispatch 3 cars to 3 different locations. The following table displays the traveling cost (in dollars) of each limousine to each area.

\text{Locations and Cars}A_1A_2A_3
L_1293722
L_2322726
L_3333425
a

Use the Hungarian algorithm to find the allocation which uses the minimum cost.

Worked Solution
Apply the idea

Start by writing the numbers in a matrix.

\begin{pmatrix} 29 & 37 & 22\\ 32 & 27 & 26 \\ 33 & 34 & 25\\ \end{pmatrix}

Subtract the lowest number in each row from the numbers in that row.

\begin{pmatrix} 29-22 & 37-22 & 22-22\\ 32-26 & 27-26 & 26-26 \\ 33-25 & 34-25 & 25-25\\ \end{pmatrix} = \begin{pmatrix} 7 & 15 & 0\\ 6 & 1 & 0 \\ 8 & 9 & 0\\ \end{pmatrix}

Subtract the lowest number in each column from the numbers in that column.

\begin{pmatrix} 7-6 & 15-1 & 0\\ 6-6 & 1-1 & 0 \\ 8-6 & 9-1 & 0\\ \end{pmatrix} = \begin{pmatrix} 1 & 14 & 0\\ 0 & 0 & 0\\ 2 & 8 & 0\\ \end{pmatrix}

Draw lines through the row and column with all zeros.

This image shows a matrix with a crossed out  line and column. Ask your teacher for more information.

The lowest remaining number is 1 so we subtract this from all the remaining numbers and add it to the number that has two lines through it to get:

\begin{pmatrix} 1-1 & 14-1 & 0\\ 0 & 0 & 0+1\\ 2-1 & 8-1& 0\\ \end{pmatrix} = \begin{pmatrix} 0 & 13 & 0\\ 0 & 0 & 1\\ 1 & 7& 0\\ \end{pmatrix} \\

We can cover all the zeros using 3 horizontal lines, one through each row. Since 3 is equal to the total number or rows, we are done. Here is the final matrix with the locations and cars: \quad \begin{matrix} A_1 & A_2 & A_3 \end{matrix} \\ \begin{matrix} L_1\\ L_2 \\ L_3 \\ \end{matrix} \begin{pmatrix} 0 & 13 & 0\\ 0 & 0 & 1\\ 1 & 7& 0\\ \end{pmatrix}

The only 0 in the row for L_3 is in column A_3, so L_3 should be allocated to A_3.

L_1 has zeros in the A_1 and A_3 columns, but A_3 is already taken, so L_1 must be allocated to A_1.

L_2 has zeros in the A_1 and A_2 columns, but A_1 is already taken, so L_2 must be allocated to A_2.

The allocation that uses the minimum cost is: L_1 \to A_1\\ L_2 \to A_2\\ L_3 \to A_3\\

b

What is the minimum cost of travel?

Worked Solution
Create a strategy

Add the numbers that correspond to the the optimum allocation found in part (a).

Apply the idea
\text{Locations and Cars}A_1A_2A_3
L_1293722
L_2322726
L_3333425

From the table we can see that the optimal allocation has the following costs: L_1 \to A_1 =29\\ L_2 \to A_2 =27\\ L_3 \to A_3 =25\\

\displaystyle \text{Minimum cost}\displaystyle =\displaystyle 29+27+25Add the costs
\displaystyle =\displaystyle \$ 81 Evaluate

Example 5

The matrix below represents a cost network.

We are going to use the Hungarian algorithm to determine the allocation that maximises the cost, by performing the following steps.

\begin{matrix} & A & B & C & D & E \end{matrix}\\ \begin{matrix} V \\ W \\ X \\ Y \\ \end{matrix} \begin{bmatrix} & 25 & 83 & 29 & 11 & 59 &\\ & 32 & 12 & 46 & 33 & 29 &\\ & 61 & 17 & 12 & 13 & 11 &\\ & 15 & 73 & 37 & 67 & 43 &\\ \end{bmatrix}

a

First invert the elements of the matrix to convert to a minimisation problem (so that we can use the Hungarian algorithm).

Worked Solution
Create a strategy

Subtract each element in the matrix from the highest element.

Apply the idea

The highest value in the matrix is 83. So we subtract each element from 83 to find the new matrix: \begin{matrix} & A \quad \quad \quad & B \quad \quad \quad& C \quad \quad \quad& D \quad \quad \quad& E \end{matrix}\\ \begin{matrix} V \\ W \\ X \\ Y \\ \end{matrix} \begin{bmatrix} & 83-25 & 83-83 & 83-29 & 83-11 & 83-59 &\\ & 83-32 & 83-12 & 83-46 & 83-33 & 83-29 &\\ & 83-61 & 83-17 & 83-12 & 83-13 & 83-11 &\\ & 83-15 & 83-73 & 83-37 & 83-67 & 83-43 &\\ \end{bmatrix} \\ \begin{matrix} & \quad A & \, B & \, C & \, D & \, E \end{matrix}\\ = \begin{matrix} V \\ W \\ X \\ Y \\ \end{matrix} \begin{bmatrix} & 58 & 0 & 54 & 72 & 24 &\\ & 51 & 71 & 37 & 50 & 54 &\\ & 22 & 66 & 71 & 70 & 72 &\\ & 68 & 10 & 46 & 16 & 40 &\\ \end{bmatrix}

b

In order to use the Hungarian algorithm, now create a square matrix from the inverted matrix.

\begin{matrix} & A & B & C & D & E \end{matrix}\\ \begin{matrix} V \\ W \\ X \\ Y \\ Z \end{matrix} \begin{bmatrix} & 58 & 0 & 54 & 72 & 24 &\\ & 51 & 71 & 37 & 50 & 54 &\\ & 22 & 66 & 71 & 70 & 72 &\\ & 68 & 10 & 46 & 16 & 40 &\\ & ⬚ & ⬚ & ⬚ & ⬚ & ⬚ &\\ \end{bmatrix}

Worked Solution
Create a strategy

Write zeros into the additional row.

Apply the idea

\begin{matrix} & A & B & C & D & E \end{matrix}\\ \begin{matrix} V \\ W \\ X \\ Y \\ Z \end{matrix} \begin{bmatrix} & 58 & 0 & 54 & 72 & 24 &\\ & 51 & 71 & 37 & 50 & 54 &\\ & 22 & 66 & 71 & 70 & 72 &\\ & 68 & 10 & 46 & 16 & 40 &\\ & 0 & 0 & 0 & 0 & 0 &\\ \end{bmatrix}

c

Now complete the initial row and column reduction.

Worked Solution
Create a strategy

Subtract the lowest number in each row from the numbers in that row.

Apply the idea

First we can subtract the lowest number in each row from the numbers in that row. If the lowest number is 0 then we do nothing in that row. \begin{matrix} & A \quad \quad & B \quad \quad & C \quad \quad & D \quad \quad & \quad E \end{matrix}\\ \begin{matrix} V \\ W \\ X \\ Y \\ Z \end{matrix} \begin{bmatrix} & 58 & 0 & 54 & 72 & 24 &\\ & 51-37 & 71-37 & 37-37 & 50-37 & 54-37 &\\ & 22-22 & 66-22 & 71-22 & 70-22 & 72-22 &\\ & 68-10 & 10-10 & 46-10 & 16-10 & 40-10 &\\ & 0 & 0 & 0 & 0 & 0 &\\ \end{bmatrix} \\ \begin{matrix} & A & B & C & D & E \end{matrix}\\ = \begin{matrix} V \\ W \\ X \\ Y \\ Z \end{matrix} \begin{bmatrix} & 58 & 0 & 54 & 72 & 24 &\\ & 14 & 34 & 0 & 13 & 17 &\\ & 0 & 44 & 49 & 48 & 50 &\\ & 58 & 0 & 36 & 6 & 30 &\\ & 0 & 0 & 0 & 0 & 0 &\\ \end{bmatrix}

Usually we would now subtract the lowest number in each column, but since each column has a 0 there is nothing to be done.

d

Complete the next stage using this strike-out pattern:

This image shows a matrix with strike-out pattern. Ask your teacher for more information.
Worked Solution
Create a strategy

Subtract the remaining lowest number from all the remaining numbers, and add it to any numbers that are crossed out twice.

Apply the idea

The lowest remaining number is 6 so we add this to all the numbers that are not crossed out, and add it to the numbers that are crossed out twice. \begin{matrix} & \quad A \quad \quad & B \quad \quad & C \quad \quad & D \quad \quad & E \end{matrix}\\ \begin{matrix} V \\ W \\ X \\ Y \\ Z \end{matrix} \begin{bmatrix} & 58-6 & 0 & 54-6 & 72-6 & 24-6 &\\ & 14 & 34+6 & 0 & 13 & 17 &\\ & 0 & 44+6 & 49 & 48 & 50 &\\ & 58-6 & 0 & 36-6 & 6-6 & 30-6 &\\ & 0 & 0+6 & 0 & 0 & 0 &\\ \end{bmatrix} \\ \begin{matrix} & \quad A & B & C & D & E \end{matrix}\\ = \begin{matrix} V \\ W \\ X \\ Y \\ Z \end{matrix} \begin{bmatrix} & 52 & 0 & 48 & 66 & 18 &\\ & 14 & 40 & 0 & 13 & 17 &\\ & 0 & 50 & 49 & 48 & 50 &\\ & 52 & 0 & 30 & 0 & 24 &\\ & 0 & 6 & 0 & 0 & 0 &\\ \end{bmatrix}

e

Determine the optimum allocation for the cost network.

V \to ⬚\\ W \to ⬚\\ X \to ⬚\\ Y \to ⬚\\ Z \to ⬚

Worked Solution
Create a strategy

Use the 0s in the matrix to find the optimal allocation.

Apply the idea

Our reduced matrix is: \begin{matrix} & \quad A & B & C & D & E \end{matrix}\\ \begin{matrix} V \\ W \\ X \\ Y \\ Z \end{matrix} \begin{bmatrix} & 52 & 0 & 48 & 66 & 18 &\\ & 14 & 40 & 0 & 13 & 17 &\\ & 0 & 50 & 49 & 48 & 50 &\\ & 52 & 0 & 30 & 0 & 24 &\\ & 0 & 6 & 0 & 0 & 0 &\\ \end{bmatrix}

Row V only has a 0 in column B so V\to B.

Row W only has a 0 in column C so W\to C.

Row X only has a 0 in column A so X\to A.

Row Y has zeros in columns B and D, but B is already taken. So Y\to D.

Row Z has zeros in columns A, C, D, and E, but A, C, and D are already taken. So Z\to E.

The optimum allocation is: V \to B\\ W \to C\\ X \to A\\ Y \to D\\ Z \to E

f

Calculate the maximum cost for the network.

Worked Solution
Create a strategy

Add the numbers that correspond to the the optimum allocation found from part (e).

Apply the idea

The original matrix was: \begin{matrix} & A & B & C & D & E \end{matrix}\\ \begin{matrix} V \\ W \\ X \\ Y \\ \end{matrix} \begin{bmatrix} & 25 & 83 & 29 & 11 & 59 &\\ & 32 & 12 & 46 & 33 & 29 &\\ & 61 & 17 & 12 & 13 & 11 &\\ & 15 & 73 & 37 & 67 & 43 &\\ \end{bmatrix} So we can see that our required costs are: V \to B =83, \, W \to C=46,\, X \to A=61,\, Y \to D=67.

\displaystyle \text{Maximum cost}\displaystyle =\displaystyle 83+46+61+67Add the costs
\displaystyle =\displaystyle \$ 257 Evaluate
Idea summary

Hungarian algorithm minimisation (from a matrix):

  1. Subtract the lowest number in each row from every number in that row.

  2. Subtract the lowest number in each column from every number in that column.

  3. Cover the 0’s with the minimum number of lines. If the number of lines required is less than the total number of rows (or columns), subtract the smallest uncovered value in the matrix from all other uncovered values, and add this value to any number covered by two lines. Repeat this step as many times as required.

  4. Make a valid assignment using the zeros in the matrix.

  5. Relate the zeros back to the data in the original matrix to answer the question in context.

Hungarian algorithm maximisation (from a matrix):

  • Find the maximum value in the matrix and subtract each element in the matrix from this maximum value.

  • Now complete the algorithm with the minimisation procedure:

    1. Subtract the lowest number in each row from every number in that row.

    2. Subtract the lowest number in each column from every number in that column.

    3. Cover the 0’s with the minimum number of lines. If the number of lines required is less than the total number of rows (or columns), subtract the smallest uncovered value in the matrix from all other uncovered values, and add this value to any number covered by two lines. Repeat this step as many times as required.

    4. Make a valid assignment using the zeros in the matrix.

    5. Relate the zeros back to the data in the original matrix to answer the question in context.

Outcomes

ACMGM110

use a bipartite graph and/or its tabular or matrix form to represent an assignment/ allocation problem; for example, assigning four swimmers to the four places in a medley relay team to maximise the team’s chances of winning

ACMGM111

determine the optimum assignment(s), by inspection for small-scale problems, or by use of the Hungarian algorithm for larger problems

What is Mathspace

About Mathspace