7.05 Assignment allocation

What do these networks have in common?

These all have a special property that is more obvious when we colour the vertices a little differently.

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

Exploration

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:

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:

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$12 hours, since Rohan takes $12$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$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$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!

 

Practice questions

QUESTION 1

QUESTION 2

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$3 agents and $3$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$3 agents and $3$3 tasks we could enumerate all possible assignments and find the minimum. There are $6$6 possible assignments when the number of agents and tasks is $3$3, so enumerating all possibilities would not be too onerous. However, for the general case of $n$n agents and $n$n jobs there are $n!$n! possibilities to check, which quickly becomes too large to check practically. For $n=4$n=4 there are $24$24 possibilities, $n=5$n=5 there are $120$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, Jenő Egerváry and Dénes Kőnig, 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.

Worked example

Example 1

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:

There are six possible allocations, but which one costs the least money overall? We start by drawing out the network:

 

The first step of the algorithm is to subtract the lowest weight of the edges coming out of their vertex from the other edges:

Harvey’s cheapest trip is $\$200$$200...	...so we subtract $\$200$$200 from all his trips.
Kiara’s cheapest trip is $\$250$$250...	...so we subtract $\$250$$250 from all her trips.
Dao’s cheapest trip is $\$300$$300...	...so we subtract $\$300$$300 from all her trips.

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

We go back to the network and do essentially the same thing, but this time looking at the destinations rather than the people. The lowest weight coming out of the Sydney vertex is $0$0, and since subtracting $0$0 doesn’t change the network we do nothing - and the same for Perth. But for the Melbourne vertex, there is something to do:

The cheapest trip to Melbourne is $\$50$$50...

...so we subtract $\$50$$50 from all Melbourne trips.

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

This leaves Harvey with a $0$0-edge to Melbourne:

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

The total, cheapest cost is $\$250+\$300+\$250=\$800$$250+$300+$250=$800. Interestingly, this involves paying the most to send someone to Sydney! This procedure finds what’s best for the group, not always the individual.

If after step $2$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.  

Practice questions

QUESTION 3

A chemical company has four factories, and each factory  can produce one of four chemicals. The cost per day (in thousands of dollars) of shipping the materials required to produce each chemical to each factory is given in the table below.

We start by getting rid of the column and row headings (we will put them back later):

We then subtract the lowest number in each row from every number in that row.  So from Row 1 we subtract $10$10 from each number, Row 2 we subtract $9$9 from each number; Row 3 we subtract $61$61 from each number; and Row 4 we subtract $34$34 from each number:

This is the same as when we subtracted the lowest weight edge for each person in the graphical example.

We then do the same with the columns.  So from Column 1, we subtract $2$2; Column 2 we subtract $0$0; Column 3 we subtract $0$0; and Column 4 we subtract $18$18.

Just like subtracting the edge weights for each task.

Now we ask: what is the least number of vertical and horizontal lines we need to cover all the $0$0’s we have made? In this example it’s three:

We need to make more zeros until we need four lines, because there are four tasks. We find the smallest number in the table not covered by any lines, which is $3$3. We subtract $3$3 from all uncovered numbers, and add $3$3 to all values covered twice by the lines, i.e. the $82$82 and the $0$0 in the top right: 

Now we need four lines to cover every $0$0, so we are ready to read off our optimum allocation! To make the minimum allocation, we need to select zeros and ensure that each row and each column contains exactly one selection. Start by looking at each row, picking the $0$0 in the row if it’s the only one:

We choose the zero in the bottom row as it is the only zero in that row.  This means that we have allocated diammonium phosphate to Mumbai.

Then do the same with the columns:

We choose the zero in row 1, column 2 because it is the only $0$0 in that column. This allocates titanium dioxide to Sydney. Similarly, we choose the zero in row 3, column 4 because it is the only $0$0 in that column, and this allocates ethylene glycol to Jakarta. This leaves only one allocation - the zero in row 2, column 1 - which allocates polyvinyl chloride to Auckland.

If we highlight the corresponding entries in the original table, we can not only read off the optimal allocation but also calculate the cost:

Sydney makes titanium dioxide, Auckland makes polyvinyl chloride, Jakarta makes ethylene glycol, and Mumbai makes diammonium phosphate, for a total (minimum!) cost of $10+14+79+34=137$10+14+79+34=137 thousand dollars per day.

Note: If during the allocation stage you cannot reduce options, that is that all available rows and columns have more than one zero, then there is more than one way to assign the tasks and you can choose arbitrarily. All valid assignments found this way will be optimal.

Practice questions

Question 4

Question 5

QUESTION 6

QUESTION 7

Worked examples

Example 3

In this example, we will look at a scenario where the number of resources is more, or less, than the number of tasks.

In either case, the variation is as simple as adding a row or column of zeros to the matrix before beginning the optimisation.

If we revisit the scenario of Example 2, but now consider the case that the company has decided that it will no longer produce ethylene glycol. 

Since the company has four factories, and each factory can produce one of four chemicals. The cost per day (in thousands of dollars of shipping the materials required to produce each chemical to each warehouse is given in the table below.

The matrix representation is now a $4$4 by $3$3 matrix: 

 

There are fewer tasks than resources so we have to make this into a square matrix by adding a column of zeros (or a row of zeros if there are fewer resources than tasks):

We then proceed in the same way as before.  After subtracting the lowest value in each column the matrix looks like this:

 

The zeros can be covered with just three lines:

We need to make more zeros until we need four lines because there are four tasks. We find the smallest number in the table not covered by any lines, which is $25$25. We subtract $25$25 from all uncovered numbers, and add $25$25 to all s covered twice by the lines (the zeros in the top right): 

 

This still only needs three lines to cover the zeros:

 

So we will repeat the last step, this time, subtracting $2$2 from uncovered values, and add $2$2 to the twice-covered values.

 

Now we need four lines to cover all of the zeros, and we can make an optimum allocation. Start by looking at each row/column, picking the $0$0 in the row/column if it’s the only one:

 

Then allocating the remaining tasks:

 

If we highlight the corresponding entries in the original table, we can not only read off the optimal allocation but also calculate the cost:

Sydney makes titanium dioxide, Auckland makes polyvinyl chloride, and Mumbai makes diammonium phosphate.  The Jakarta factory is no longer required.

Example 4

In this final example, we will use the Hungarian algorithm to find an optimum allocation in a scenario that we want to maximise some quantity. 

The optimum allocation might require finding the maximum value in scenarios such as a business wanting to maximise revenue or profits, a farmer wanting the highest possible grain yield from the available paddocks, a factory aiming to produce the greatest number of parts with available machinery and many others.

We will consider a sales manager for a toy manufacturer, and you currently have three salespeople on the road meeting buyers.

The salespeople are Alan, Beverley and Cat.  During a sales campaign, they can each visit one of three stores in Denver, Edmonton and Fargo to launch the new range of Gizmo toys. 

Based on the results of previous campaigns, the expected sales (units) for each of the salespersons in each of the stores is shown in the table below:

How should the sales manager direct the salespeople in order to achieve maximum sales from the campaign?

We will represent this table as a matrix:

To adapt the Hungarian algorithm to solve a maximisation problem, an initial conversion is performed:

1. Find the maximum value in the matrix;
2. Subtract each element in the matrix from this maximum value.

The converted matrix produced represents a cost, in this case, a loss of sales that we can minimise using the standard algorithm.

If necessary, for a problem where the number of tasks is not equal to the number of resources, the conversion step should be done before the matrix is extended with a row or column of zeros.

For the toy sales manager, the maximum value is $600$600.  Subtracting each value from $600$600 produces this new matrix:

Reducing the rows and columns produces this reduced matrix, from which the optimum solution can be extracted:

The original table can be restored with the optimum allocation highlighted.

With Alan selling to the Fargo store, Beverley selling to Edmonton and Cat selling to Denver, we can see that the optimum allocation produces the expected sales of $600+200+350=1150$600+200+350=1150 units.

Practice question

Question 8