Hungarian algorithm

Hungarian algorithm

Also called algorithm de Kühn, l’algorithme hongrois, ou méthode hongroise résout des problèmes d’affectation de type table de coûts. Considérons un certain nombre de machines et autant de tâches. Chaque machine exécute une tâche à un certain coût. L’objectif est de déterminer la machine sur laquelle s’exécutera chaque tâche, en parallèle.

Ce problème étant similaire à un problème de couplage dans un graph, il répond au critère de König pour la couverture nodale de poids minimum. L’objectif est donc de trouver un élément par ligne et colonne dans la table telle que la somme des coûts soit minimale. Si l’on part d’un problème de maximisation, il faudra inverser les coûts afin de retomber sur un problème de minimisation.

Let us take a simple example in order to show the process of the algorithm. Let 5 machines (row) and 5 tasks (column) give 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

We subtract from each line the smallest element of the line. The more we subtract from each column the smaller element of the column.
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 row and per column.

Hungarian Algorithm Step 2: Find a Workable Solution

We are looking for the line with the fewest non-crossed zeros. In the event of a tie, we will take the highest line.

  1. We surround one of the zeros of this line (arbitrarily the one furthest to the left).
  2. All zeros in the same row and column as the one selected are crossed out.
  3. We start again until all the zeros are boxed or crossed out.

If we have framed a zero by row and by 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:

  1. We mark any line that does not contain any framed zero.
  2. Any column with a crossed out zero is marked on a marked row.
  3. We mark any row having a framed zero in a marked column.
  4. Repeat 2 and 3 until no more changes.

A line is then drawn on any unmarked line and on any marked column. In our example, row 1 and 2 are marked, as well as column 4. Double-marked items 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.

  1. We subtract from all the boxes of this table the smallest element thereof.
  2. This element is added to all the boxes of the table crossed out in both directions (accompanied by a star).

Steps 2 to 4 are repeated 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.

Hungarian algorithm Kühn's algorithm Hungarian method assignment problems König's criterion

To share
en_GBEN
%d bloggers like this: