Introduction
What do these networks have in common?
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 poster | Writing the report | Writing the speech | |
|---|---|---|---|
| \text{Paula} | 10 | 5 | 8 |
| \text{Rohan} | 6 | 7 | 12 |
| \text{Erin} | 9 | 8 | 5 |
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 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:
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 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.
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}
Example 2
Consider the following bipartite graph.
Which of the following allocations agree with the bipartite graph?
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:
Subtract the lowest weight of edges coming out of each vertex on the left from the others.
Subtract the lowest weight of edges coming out of each vertex on the right from the others.
Make a valid assignment using the edges of weight zero.
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:
| Sydney | Melbourne | Perth | |
|---|---|---|---|
| \text{Harvey} | \$200 | \$250 | \$320 |
| \text{Kiara} | \$280 | \$300 | \$250 |
| \text{Dao} | \$300 | \$470 | \$510 |
Which allocation costs the least money overall?
These steps can be used to solve simple assignment problems using the graphical procedure:
Subtract the lowest weight of edges coming out of each vertex on the left from the others.
Subtract the lowest weight of edges coming out of each vertex on the right from the others.
Make a valid assignment using the edges of weight zero.
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):
Subtract the lowest number in each row from every number in that row.
Subtract the lowest number in each column from every number in that column.
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.
Make a valid assignment using the zeros in the matrix.
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:
Subtract the lowest number in each row from every number in that row.
Subtract the lowest number in each column from every number in that column.
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.
Make a valid assignment using the zeros in the matrix.
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_1 | A_2 | A_3 |
|---|---|---|---|
| L_1 | 29 | 37 | 22 |
| L_2 | 32 | 27 | 26 |
| L_3 | 33 | 34 | 25 |
Use the Hungarian algorithm to find the allocation which uses the minimum cost.
What is the minimum cost of travel?
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}
First invert the elements of the matrix to convert to a minimisation problem (so that we can use the Hungarian algorithm).
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}
Now complete the initial row and column reduction.
Complete the next stage using this strike-out pattern:
Determine the optimum allocation for the cost network.
V \to ⬚\\ W \to ⬚\\ X \to ⬚\\ Y \to ⬚\\ Z \to ⬚
Calculate the maximum cost for the network.
Hungarian algorithm minimisation (from a matrix):
Subtract the lowest number in each row from every number in that row.
Subtract the lowest number in each column from every number in that column.
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.
Make a valid assignment using the zeros in the matrix.
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:
Subtract the lowest number in each row from every number in that row.
Subtract the lowest number in each column from every number in that column.
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.
Make a valid assignment using the zeros in the matrix.
Relate the zeros back to the data in the original matrix to answer the question in context.