Assignment problem: Hungarian method 3
Assignment problem: Hungarian Method Nui Ruppert (Mtk_Nr.: 373224) David Lenh (Mtk_Nr.: 368343) Amir Farshchi Tabrizi (Mtk-Nr.: 372894)
In this OR-Wiki entry we're going to explain the Hungarian method with 3 examples. In the first example you'll find the optimal solution after a few steps with the help of the reduced matrix. The second example illustrates a complex case where you need to proceed all the steps of the algorithm to get to an optimal solution. Finally in the third example we will show how to solve a maximization problem with the Hungarian method.
Inhaltsverzeichnis
Introduction
The Hungarian method is a combinatorial optimization algorithm which was developed and published by Harold Kuhn in 1955. This method was originally invented for the best assignment of a set of persons to a set of jobs. It is a special case of the transportation problem. The algorithm finds an optimal assignment for a given “n x n” cost matrix. “Assignment problems deal with the question how to assign n items (e.g. jobs) to n machines (or workers) in the best possible way. […] Mathematically an assignment is nothing else than a bijective mapping of a finite set into itself […]” [1]
The assignment constraints are mathematically defined as:
To make clear how to solve an assignment problem with the Hungarian algorithm we will show you the different cases with several examples which can occur .
Example 1 – Minimization problem
In this example we have to assign 4 workers to 4 machines. Each worker causes different costs for the machines. Your goal is to minimize the total cost to the condition that each machine goes to exactly 1 person and each person works at exactly 1 machine. For comprehension: Worker 1 causes a cost of 6 for machine 1 and so on …
To solve the problem we have to perform the following steps:
Step 1 – Subtract the row minimum from each row.
Step 2 – Subtract the column minimum from each column from the reduced matrix.
The idea behind these 2 steps is to simplify the matrix since the solution of the reduced matrix will be exactly the same as of the original matrix.
Step 3 – Assign one “0” to each row & column.
Now that we have simplified the matrix we can assign each worker with the minimal cost to each machine which is represented by a “0”.
- In the first row we have one assignable “0” therefore we assign it to worker 3.
- In the second row we also only have one assignable “0” therefore we assign it to worker 4.
- In the third row we have two assignable “0”. We leave it as it is for now.
- In the fourth row we have one assignable “0” therefore we assign it. Consider that we can only assign each worker to each machine hence we can’t allocate any other “0” in the first column.
- Now we go back to the third row which now only has one assignable “0” for worker 2.
As soon as we can assign each worker to one machine, we have the optimal solution. In this case there is no need to proceed any further steps.
Remember also, if we decide on an arbitrary order in which we start allocating the “0”s then we may get into a situation where we have 3 assignments as against the possible 4. If we assign a “0” in the third row to worker 1 we wouldn’t be able to allocate any “0”s in column one and row two.
The rule to assign the “0”:
- If there is an assignable “0”, only 1 assignable “0” in any row or any column, assign it.
- If there are more than 1, leave it and proceed.
This rule would try to give us as many assignments as possible.
Now there are also cases where you won’t get an optimal solution for a reduced matrix after one iteration. The following example will explain it.
Example 2 – Minimazation problem
In this example we have the fastest taxi company that has to assign each taxi to each passenger as fast as possible. The numbers in the matrix represent the time to reach the passenger.
We proceed as in the first example.
Step 1 – Subtract the row minimum from each row.
Step 2 – Subtract the column minimum from each column from the reduced matrix.
Iteration 1:
Step 3 – Assign one “0” to each row & column.
Now we have to assign the “0”s for every row respectively to the rule that we described earlier in example 1.
- In the first row we have one assignable “0” therefore we assign it and no other allocation in column 2 is possible.
- In the second row we have one assignable “0” therefore we assign it.
- In the third row we have several assignable “0”s. We leave it as it is for now and proceed.
- In the fourth and fifth row we have no assignable “0”s.
Now we proceed with the allocations of the “0”s for each column.
- In the first column we have one assignable “0” therefore we assign it. No other “0”s in row 3 are assignable anymore.
Now we are unable to proceed because all the “0”s either been assigned or crossed. The crosses indicate that they are not fit for assignments because assignments are already made.
We realize that we have 3 assignments for this 5x5 matrix. In the earlier example we were able to get 4 assignments for a 4x4 matrix. Now we have to follow another procedure to get the remaining 2 assignments (“0”).
Step 4 – Tick all unassigned rows.
Step 5 – If a row is ticked and has a “0”, then tick the corresponding column (if the column is not yet ticked).
Step 6 – If a column is ticked and has an assignment, then tick the corresponding row (if the row is not yet ticked).
Step 7 - Repeat step 5 and 6 till no more ticking is possible.
In this case there is no more ticking possible and we proceed with the next step.
Step 8 – Draw lines through unticked rows and ticked columns. The number of lines represents the maximum number of assignments possible.
Step 9 – Find out the smallest number which does not have any line passing through it. We call it Theta. Subtract theta from all the numbers that do not have any lines passing through them and add theta to all those numbers that have two lines passing through them. Keep the rest of them the same.
(With this step we create a new “0”)
With the new assignment matrix we start to assign the “0”s after the explained rules. Nevertheless we have 4 assignments against the required 5 for an optimal solution. Therefore we have to repeat step 4 – 9.
Iteration 2:
Step 3 – Assign one “0” to each row & column.
Step 4 – Tick all unassigned row.
Step 5 – If a row is ticked and has a “0”, then tick the corresponding column (if the column is not yet ticked).
Step 6 – If a column is ticked and has an assignment, then tick the corresponding row (if the row is not yet ticked).
Step 7 - Repeat step 5 and 6 till no more ticking is possible.
Step 8 – Draw lines through unticked rows and ticked columns. The number of lines represents the maximum number of assignments possible.
Step 9 – Find out the smallest number which does not have any line passing through it. We call it Theta. Subtract theta from all the numbers that do not have any lines passing through them and add theta to all those numbers that have two lines passing through them. Keep the rest of them the same.
Note: The indices of the ticks show you the order we added them.
Iteration 3:
Step 3 – Assign one “0” to each row & column.
Step 4 – Tick all unassigned row.
Step 5 – If a row is ticked and has a “0”, then tick the corresponding column (if the column is not yet ticked).
Step 6 – If a column is ticked and has an assignment, then tick the corresponding row (if the row is not yet ticked).
Step 7 - Repeat step 5 and 6 till no more ticking is possible.
Step 8 – Draw lines through unticked rows and ticked columns. The number of lines represents the maximum number of assignments possible.
Step 9 – Find out the smallest number which does not have any line passing through it. We call it Theta. Subtract theta from all the numbers that do not have any lines passing through them and add theta to all those numbers that have two lines passing through them. Keep the rest of them the same.
Iteration 4:
Step 3 – Assign one “0” to each row & column.
Step 4 – Tick all unassigned row.
Step 5 – If a row is ticked and has a “0”, then tick the corresponding column (if the column is not yet ticked).
Step 6 – If a column is ticked and has an assignment, then tick the corresponding row (if the row is not yet ticked).
Step 7 - Repeat step 5 and 6 till no more ticking is possible.
Step 8 – Draw lines through unticked rows and ticked columns. The number of lines represents the maximum number of assignments possible.
Step 9 – Find out the smallest number which does not have any line passing through it. We call it Theta. Subtract theta from all the numbers that do not have any lines passing through them and add theta to all those numbers that have two lines passing through them. Keep the rest of them the same.
After the fourth iteration we assign the “0”s again and now we have an optimal solution with 5 assignments.
The solution:
- Taxi1 => Passenger1 - duration 12
- Taxi2 => Passenger4 - duration 11
- Taxi3 => Passenger2 - duration 8
- Taxi4 => Passenger3 - duration 14
- Taxi5 => Passenger5 - duration 11
If we define the needed duration as costs, the minimal cost for this problem is 56.
Example 3 – Maximization problem
Furthermore the Hungarian algorithm can also be used for a maximization problem in which case we first have to transform the matrix. For example a company wants to assign different workers to different machines. Each worker is more or less efficient with each machine. The efficiency can be defined as profit. The higher the number, the higher the profit.
As you can see, the maximal profit of the matrix is 13. The simple twist that we do is rather than try to maximize the profit, we’re going to try to minimize the profit that you don’t get. If every value is taken away from 13, then we can minimize the amount of profit lost.
We receive the following matrix:
From now on we proceed as usual with the steps to get to an optimal solution.
Step 1 – Subtract the row minimum from each row.
Step 2 – Subtract the column minimum from each column from the reduced matrix.
Step 3 – Assign one “0” to each row & column.
With the determined optimal solution we can compute the maximal profit:
- Worker1 => Machine2 - 9
- Worker2 => Machine4 - 11
- Worker3 => Machine3 - 13
- Worker4 => Machine1 - 7
Maximal profit is 40.
Summary
Step 1 – Subtract the row minimum from each row.
Step 2 – Subtract the column minimum from each column from the reduced matrix.
Step 3 – Assign one “0” to each row & column.
Step 4 – Tick all unassigned row.
Step 5 – If a row is ticked and has a “0”, then tick the corresponding column (if the column is not yet ticked).
Step 6 – If a column is ticked and has an assignment, then tick the corresponding row (if the row is not yet ticked).
Step 7 - Repeat step 5 and 6 till no more ticking is possible.
Step 8 – Draw lines through unticked rows and ticked columns. The number of lines represents the maximum number of assignments possible.
Step 9 – Find out the smallest number which does not have any line passing through it. We call it Theta. Subtract theta from all the numbers that do not have any lines passing through them and add theta to all those numbers that have two lines passing through them. Keep the rest of them the same.
Step 3 – Assign one “0” to each row & column.
The optimal solution is found if there is one assigned “0” for each row and each column.
References
[1] Linear Assignment Problems and Extensions, Rainer E. Burkard, Eranda Cela
[2] Operations Research Skript TU Kaiserslautern, Prof. Dr. Oliver Wendt
[3] The Hungarian method for the assignment problem, H. W. Kuhn, Bryn Mawr College
Fundamental of Operations Research, Lec. 16, Prof. G. Srinivasan
