Hungarian algorithm
Also called algorithm of Kühn, the Hungarian algorithm, or Hungarian method solves assignment problems of the cost table type. Consider a number of machines and as many tasks. Each machine performs a task at a certain cost. The objective is to determine the machine on which each task will run, in parallel.
Let's take a simple example to show the process of the algorithm. Consider 5 machines (row) and 5 tasks (column) giving the following cost table:
|
17
|
15
|
9
|
5
|
12
|
|
16
|
16
|
10
|
5
|
10
|
|
12
|
15
|
14
|
11
|
5
|
|
4
|
8
|
14
|
17
|
13
|
|
13
|
9
|
8
|
12
|
17
|
Step 1 Hungarian algorithm: reduction of the initial table
|
12
|
9
|
4
|
0
|
7
|
|
11
|
10
|
5 |
0
|
5
|
|
7
|
9
|
9
|
6
|
0
|
|
0
|
3
|
10
|
13
|
9
|
|
5
|
0
|
0
|
4
|
9
|
This standardization of machine and task costs makes it possible to have at least one zero per line and per column.
Hungarian Algorithm Step 2: Find a Workable Solution
We are looking for the line with the fewest unslashed zeros. In case of a tie, the highest line will be taken.
- We surround one of the zeros of this line (arbitrarily the one furthest to the left).
- All zeros in the same row and column as the one selected are crossed out.
- Repeat until all zeros are boxed or crossed out.
If we circled a zero per line and per column, we have an optimal solution. Otherwise we go to step 3.
|
12
|
9
|
4
|
0
|
7
|
|
11
|
10
|
5 |
-0-
|
5
|
|
7
|
9
|
9
|
6
|
0
|
|
0
|
3
|
10
|
13
|
9
|
|
5
|
0
|
-0-
|
4
|
9
|
Step 3 Hungarian algorithm: creation of the pivots
The sub-table allows by subtraction to have a configuration making it possible to find an optimal solution. The construction of the pivots is done as follows:
- We mark any line that does not contain any framed zero.
- Any column with a crossed out zero is marked on a marked row.
- We mark any row having a framed zero in a marked column.
- Repeat 2 and 3 until there are no more changes.
A line is then drawn on any unmarked row and on any marked column. In our example, row 1 and 2 are marked, as well as column 4. Items marked twice are marked with a star.
|
12
|
9
|
4
|
-0-
|
7
|
|
11
|
10
|
5 |
-0-
|
5
|
|
-7-
|
-9-
|
-9-
|
*-6-*
|
-0-
|
|
-0-
|
-3-
|
-10-
|
*-13-*
|
-9-
|
|
-5-
|
-0-
|
-0-
|
*-4-*
|
-9-
|
Step 4 Hungarian algorithm: modification of the table
The cells not crossed by a line constitute a partial table.
- We subtract from all the boxes of this table the smallest element thereof.
- This element is added to all the squares of the table crossed out in both directions (accompanied by a star).
We repeat steps 2 to 4 until an optimal result is obtained. In our example, we get an optimal result after the first iteration.
|
8
|
5
|
0
|
0
|
3
|
|
7
|
6
|
1 |
0
|
1
|
|
7
|
9
|
9
|
10
|
0
|
|
0
|
3
|
10
|
17
|
9
|
|
5
|
0
|
0
|
8
|
9
|
The minimum allocation is calculated from the initial table: 9+5+5+4+9 = 32.
The following figure shows the changes in the bipartite graph with the Hungarian algorithm.
