Assignment problem: Hungarian method 3
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 which can occur with several examples.
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.
