Hungarian method

This article or section needs to be revised. Details should be given on the talk page. Please help to improve it , and then remove this flag.

The Hungarian method , also called Kuhn-Munkres algorithm , is an algorithm for solving weighted assignment problems on bipartite graphs . This problem class can be formulated as a special case of linear optimization , the Hungarian method is then an adapted primal-dual solution method. The original implementation had a complexity of , with suitable data structures and optimized subroutines this could be reduced to. ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{3})}$

The Hungarian method was developed in 1955 by Harold W. Kuhn taking into account previous ideas of the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry and improved by James Munkres in 1957, following an analysis of the running time.

Task

There are two groups of objects, mostly the same number and roughly referred to as "sources" S (after English: "source") and "goals" T (after English: "target"), between which a one-to-one assignment must be established , d. H. each source is assigned at most one destination and each destination is assigned at most one source. Every (permissible) assignment of a “source” s to a “destination” t has a price or a profit c (s, t) . The goal of the algorithm is, depending on the type of problem, to minimize the total price (= sum of the individual prices) of the assignment or to maximize the total profit (= sum of the individual profits) of the assignment. A maximum number of pairs must always be formed.

Illustrative examples

Common examples are

• the marriage problem , in which the two groups consist of women and men willing to marry and a connection is assigned a "sympathy measure" as a profit variable. The aim is then to find as many couples as possible with a maximum “sympathy sum”.
• the auction model , in which a number of art objects or other goods are to be distributed among an equal number of art lovers or general buyers, with each art lover having an asking price for the objects of interest. The aim of the auction is to achieve a maximum total price.
• the job problem in which a number of work orders have to be distributed among an equal number of workers or machines. The evaluation can either represent the suitability of a worker for the job, or the costs of executing a job on a machine.

Mathematical modeling

There are two equivalent abstract models of the assignment problem. On the one hand, sources and destinations can be understood as nodes of a bipartite graph whose edges are the permissible assignments. Each edge is weighted with the evaluation of this assignment.

A second representation collects the data of the assignment problem in a square matrix . Each row corresponds to a source, each column to a target (or vice versa), and each matrix component contains the evaluation of the assignment of its source to its target. This matrix is ​​also a weighted adjacency matrix of the edge-weighted bipartite graph . Missing edges of the graph, i.e. H. Inadmissible assignments are represented by very small negative numbers or the artificial value in the matrix. ${\displaystyle -\infty }$

Different number of sources and destinations

But there are also cases in which the initial problem does not have a square shape: Employees take aptitude tests for positions to be filled ( ). In these cases the problem is either solved by the graph-theoretical version of the Hungarian method or the matrix is ​​artificially square by introducing dummy positions (“no position”). Dummy positions are usually filled with the largest number available from the matrix. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k<n}$ ${\displaystyle n-k}$

Matrix transversals

If a maximum assignment (maximum matching) has been found, there is exactly one element in each row and each column of the matrix that belongs to the optimal solution; such a group of positions is also referred to as the transversal of the matrix. Therefore, the problem can also be formulated differently: Rearrange the row or column vectors so that the sum of the elements in the main diagonal is maximum. From this it is immediately apparent that in a x is matrix just as many ways to arrange the row or column vectors, as permutations of n are elements, ie . Except in the case of small matrices, there is almost no point in finding the optimal solution by calculating all possibilities. With a 10 × 10 matrix, there are almost 3.63 million (3,628,800) permutations to be considered. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n!}$

11 calculation steps without formulas

1. If you are looking for a minimum (as in the examples below), then skip this step. Find the "largest number" in the matrix. Create a new matrix and fill it with the differences between the “largest number” and the old element at this point. If no mistake was made, the new matrix only has positive values, and zeros are now at the places where the “largest number” was.
2. Form the column minima (see example 1 matrix 1).
3. Subtract the respective column minimum from each element of a column (see example 1 matrix 2).
4. Form the new line minima.
5. Subtract the respective line minimum from each element of a line (see example 1 matrix 3).
6. Find a combination of zeros in such a way that exactly one zero is selected in every row and in every column. A tip on this: If there is only one single zero in a row or column , it must of course be in the solution. Mark these zeros first, then you will find the rest of the permissible assignments a little easier.
7. If there is such a combination of zeros, the positions of the zeros in this combination represent the optimal assignments, and the process is ended. (This is the case in Example 1, which is why the following calculation steps are not necessary in Example 1).
8. If there is no such combination of zeros, because no zeros can be found in certain rows or columns that do not violate the condition of point 6, then find the minimum number of (horizontal and vertical) lines with which all zeros in the matrix are deleted can. If at least dashes are required in a matrix to delete all zeros, then this matrix already contains the optimal solution. ${\displaystyle n\times n}$ ${\displaystyle n}$
9. Find the minimum of the coefficients that are not deleted.
10. Now a new matrix is ​​made and the coefficients are transferred from the original matrix. Coefficients that were crossed out by exactly one line are to be adopted unchanged in the new matrix. In the case of coefficients not previously deleted , the minimum determined in the previous point must be subtracted . On the other hand, if a coefficient is struck by two lines , the previously determined minimum must be added . ${\displaystyle n\times n}$
11. Go to point 6, transform the matrix and try again to find a valid combination of zeros in the new matrix.

Note: For reasons of symmetry, the terms "rows" and "columns" can be interchanged in points 2 to 5.

example 1

Father overhears an argument from the nursery. His four children Anna, Berta, Chiara and David quarrel once again over the toys: the train, the grocery store, the doll and the zoo. Since there was no peaceful settlement, father intervened and asked the children how they ranked their preferences with regard to the four toys. From these rankings, father creates a 4 × 4 matrix and tries to minimize the "sum of tears" by cleverly assigning the toys to the children. He can use the Hungarian method for this project, as shown in the following figure.

Lines: toys E, K, P and Z

Columns: children A, B, C and D

Column elements: ranking of children's preferences A, B, C, D for toys E, K, P, Z: 1 means highest, 4 means lowest preference.

Ranking of preferences

	A.	B.	C.	D.	min
E.	1	1	1	2	1
K	3	2	4th	1	1
P	4th	4th	2	4th	2
Z	2	3	3	3	2
min	1	1	1	1

Reduction of the column elements by the column minimum

	A.	B.	C.	D.	min
E.	0	0	0	1	0
K	2	1	3	0	0
P	3	3	1	3	1
Z	1	2	2	2	1
min	0	0	0	0

Reduction of the line elements by the line minimum

	A.	B.	C.	D.	min
E.	0	0	0	1	0
K	2	1	3	0	0
P	2	2	0	2	0
Z	0	1	1	1	0
min	0	0	0	0

optimal assignment

child	toy	Preference
A.	Z	2
B.	E.	1
C.	P	2
D.	K	1

The optimal assignment of the toys to the children, which minimizes the "overall frustration" in the children's room, is:

Anna gets the zoo, Berta the train, Chiara the doll, David plays with the grocery store.

In this case, any alternative assignment would be worse.

The ideal total rank would be 4 if each child got their favorite toy. This assignment is not possible, otherwise there would have been no dispute. That would only work if there was only one 1 in each row and column of the output matrix. The minimum rank sum is therefore 6.

Example 2

Three workpieces are to be processed on one of three available machines. What is sought is the optimal (minimum total cost) assignment of the workpieces to the machines. A matrix is ​​then given for the machining costs from workpiece to machine . ${\displaystyle A}$ ${\displaystyle i}$ ${\displaystyle j}$

Also to solve some cases the postman problem ( chinese postman problem- ) the Hungarian algorithm can be used.

Method with formulas

The square matrix of size is given . Without loss of generality, an assignment with a minimum total is sought, which are a permutation of . ${\displaystyle C=(c_{ij})}$ ${\displaystyle n\times n}$ ${\displaystyle j\to s_{j},\ j=1,\ldots ,n}$ ${\displaystyle \textstyle \sum _{j=1}^{n}c_{s_{j},j}}$ ${\displaystyle s_{j}}$ ${\displaystyle \{1,\ldots ,n\}}$

If the sum is to be maximized, it can be replaced by. ${\displaystyle C}$ ${\displaystyle -C}$

The basis of this procedure is that the optimal assignment does not change under certain changes in the matrix, only the optimal value. These changes are indicated by node potentials or dual variables for the rows and for the columns. The modified matrix then has the components . In the sum of each edge-maximum assignment, each node potential occurs exactly once, so that the change in the objective function is a constant. ${\displaystyle u_{1},u_{2},\dots ,u_{n}}$ ${\displaystyle v_{1},v_{2},\dots ,v_{n}}$ ${\displaystyle {\tilde {c}}_{i,j}=c_{ij}-u_{i}-v_{j}}$

If the entries are nonnegative and all node potentials are also nonnegative, then the modified matrix is also called a reduction. The aim is to bring as many components as possible to the value zero in the reduced matrix and to construct the assignment under these. ${\displaystyle C}$ ${\displaystyle {\tilde {C}}}$

Hand bill

1. Subtract the minimum from in each row and column. ${\displaystyle C}$
2. Mark as many zeros as possible in the reduced matrix with an asterisk ( ), unless there is already an asterisk in the row or in the column. ${\displaystyle \star }$
3. If stars could be set, then they indicate an optimal assignment. The calculation is now complete. ${\displaystyle n}$
4. Put a margin marker (plus sign) for each column that contains an asterisk.
5. Find the minimum of the unmarked elements. ${\displaystyle h}$
6. At add to all double-bordered elements and subtract from all non-bordered elements. ${\displaystyle h>0}$ ${\displaystyle h}$ ${\displaystyle h}$
7. Mark an unmarked zero with a dash.
8. If there is already an asterisk in the line of this zero, delete the edge marking of the star, set an edge marking for this line and go to step 5.
9. Mark the zero with an asterisk.
10. If there is another star within this column, for example in a line , delete this star, select the dashed zero in line and go to step 9. ${\displaystyle i}$ ${\displaystyle i}$
11. Delete all dashes and line markers and go to step 3.

With each jump from step 11 to step 3, one more item is assigned. Because of the time-consuming minimum search in step 5 and the matrix changes in step 6, the complexity of this procedure is . ${\displaystyle {\mathcal {O}}(n^{4})}$

example

Deleted column markings are shown with . Let the matrix already reduced according to step 1 be ${\displaystyle \oplus }$

${\displaystyle \left[{\begin{array}{*{4}c}0&0&0&0\\0&1&3&3\\0&5&5&9\\0&1&3&7\end{array}}\right]}$. Steps 2 and 4 result . Steps 5-8 provide . Well will . Step 6 brings . Steps 7-11 provide . Steps 3–8 result . Now will . Step 6 provides . With steps 7 and 8 one can get. Bring steps 5–10 . In you can see the result of the further reassignment according to steps 9 and 10, and this is optimal. ${\displaystyle \left[{\begin{array}{*{4}c}0&\star &0&0\\\star &1&3&3\\0&5&5&9\\0&1&3&7\\+&+\end{array}}\right]}$ ${\displaystyle \left[{\begin{array}{*{5}c}0&\star &0'&0&+\\\star &1&3&3\\0&5&5&9\\0&1&3&7\\+&\oplus \end{array}}\right]}$ ${\displaystyle h=1}$ ${\displaystyle \left[{\begin{array}{*{5}c}1&\star &0'&0&+\\\star &0&2&2\\0&4&4&8\\0&0&2&6\\+&\oplus \end{array}}\right]}$ ${\displaystyle \left[{\begin{array}{*{4}c}1&0&\star &0\\\star &0&2&2\\0&4&4&8\\0&\star &2&6\\+\end{array}}\right]}$ ${\displaystyle \left[{\begin{array}{*{5}c}1&0&\star &0'&+\\\star &0&2&2\\0&4&4&8\\0&\star &2&6\\+&+&\oplus \end{array}}\right]}$ ${\displaystyle h=2}$ ${\displaystyle \left[{\begin{array}{*{5}c}3&2&\star &0'&+\\\star &0&0&0\\0&4&2&6\\0&\star &0&4\\+&+&\oplus \end{array}}\right]}$ ${\displaystyle \left[{\begin{array}{*{5}c}3&2&\star &0'&+\\\star &0&0'&0&+\\0&4&2&6\\0&\star &0&4\\\oplus &+&\oplus \end{array}}\right]}$ ${\displaystyle \left[{\begin{array}{*{5}c}3&2&\star &0'&+\\0&0&0'&0&+\\\star &4&2&6\\0&\star &0&4\\\oplus &+&\oplus \end{array}}\right]}$ ${\displaystyle \left[{\begin{array}{*{5}c}3&2&0&\star &+\\0&0&\star &0&+\\\star &4&2&6\\0&\star &0&4\\\oplus &+&\oplus \end{array}}\right]}$

Machine solution

Two vectors are required to assign the stars and save the line markings . This means that there is no asterisk in the column , while it means that there is no zero with a dash in the -th line. Otherwise enter and the position of the star or stroke in column or row to. Line is bordered if and only if is. Column is edge-marked if and only if applies. ${\displaystyle s,z\in \mathbb {N} ^{n}}$ ${\displaystyle s_{j}=0}$ ${\displaystyle j}$ ${\displaystyle z_{i}=0}$ ${\displaystyle i}$ ${\displaystyle s_{j}}$ ${\displaystyle z_{i}}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle z_{i}>0}$ ${\displaystyle j}$ ${\displaystyle s_{j}>0\land z_{s_{j}}=0}$

In order to keep the complexity low and to reduce it to, additional vectors for the node potentials as well as a vector for faster minimum search in step 5 are used for the machine calculation . contain the minimum of unmarked elements for each line. Thus, lines marked in the margin are to be excluded. This vector can be initialized in step 3 or 4. Step 1 is replaced as follows: ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle u,v\in \mathbb {R} ^{n}}$ ${\displaystyle m\in \mathbb {R} ^{n}}$ ${\displaystyle m}$ ${\displaystyle h=\min \limits _{i}m_{i}}$ ${\displaystyle m}$

For set . ${\displaystyle j=1,\ldots ,n}$ ${\displaystyle v_{j}:=\min \limits _{i}c_{ij}}$

For set . ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle u_{i}:=\min \limits _{j}(c_{ij}-v_{j})}$

In steps 2–10, the reduced weights are used for each calculation. In particular, step 6 is reduced at to ${\displaystyle {\tilde {c}}_{ij}=c_{ij}-u_{i}-v_{j}}$ ${\displaystyle h>0}$

For : ${\displaystyle j=1,\ldots ,n}$

a) If column is not marked at the edge, add to . ${\displaystyle j}$ ${\displaystyle h}$ ${\displaystyle v_{j}}$

b) If line is highlighted, subtract from . ${\displaystyle j}$ ${\displaystyle h}$ ${\displaystyle u_{j}}$

c) Subtract from (at least in unmarked lines). ${\displaystyle h}$ ${\displaystyle m_{j}}$

If a column marking is to be canceled in step 8, the adjustment requires only linear effort, namely comparison with the entries in the relevant column and, if necessary, their adoption . ${\displaystyle m}$ ${\displaystyle m}$

Auxiliary procedures for complex tasks

Example 2 can be easily solved in a few seconds. However, the degree of complexity of finding the independent zeros (computation steps point 6) increases rapidly with the dimension of the × matrix. Without the appropriate software, a manual process sometimes fails to find a solution for a relatively long time. A solution, which in many cases already represents the optimal solution, is achieved with the Habr method , which is easier to program in a spreadsheet than the Hungarian method from step 8. On the other hand, finding the optimal solution by randomly searching for sets of permissible combinations , is highly unlikely for larger matrices; for a × matrix there are exactly admissible sets. With a 15 × 15 matrix, the number of permitted sets is 1.3 trillion. As a rule, at most some, but at least one of them are optimal. The more complex the task, the more the effort involved in finding the optimal solution must be included in the calculation. In practice, therefore, one is often satisfied with suboptimal solutions close to the presumed optimum, because one has the guarantee that they will be found much more quickly, which often more than compensates for the losses resulting from the selection of a less than optimal solution. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n!}$

The frequency method according to Habr et al.

The basic idea of ​​this method is related to that of the analysis of variance , in that each value of a matrix is ​​assessed according to its deviations from the mean values. Since it is important to know whether the value is above or below a mean value, we do not work with squares of differences, but with the differences themselves. The mean value of the relevant row and the mean value of the relevant column are subtracted from each value of the output matrix and the mean value of the entire matrix is ​​added, so that one arrives at a new matrix whose mean values ​​over the rows, the columns and over the matrix all contain the value Have zero: ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle y(ij)=x(ij)-\mu (x(i.))-\mu (x(.j))+\mu (x(ij))}$

This transformation relativizes the value of a cell in the matrix via its rank in row, column and overall matrix; In the optimization calculation, differences are more significant than absolute values.

The more negative a value is, the more it will belong to the optimum when viewed individually. Now those negative values ​​are sought, the sum of which is minimal or at least as low as possible. Here, too, it should be noted that only one value is allowed per row and column. It can happen that positive values ​​must also be included in the assignment. ${\displaystyle y(ij)}$

Unlike the Hungarian method, Habr's method is not tied to square matrices. It solves example 1 with only 1 matrix transformation:

Method by Habr

Ranking of preferences
Matrix x

	A.	B.	C.	D.	${\displaystyle \mu }$
E.	1	1	1	2	1.25
K	3	2	4th	1	2.50
P	4th	4th	2	4th	3.50
Z	2	3	3	3	2.75
${\displaystyle \mu }$	2.5	2.5	2.5	2.5	2.5

Matrix y

	A.	B.	C.	D.	${\displaystyle \mu }$
E.	−0.25	−0.25	−0.25	0.75	0.00
K	0.5	−0.5	1.5	−1.5	0.00
P	0.5	0.5	−1.5	0.5	0.00
Z	−0.75	0.25	0.25	0.25	0.00
${\displaystyle \mu }$	0	0	0	0	0.00

The minimum sum is −4.

Individual evidence

1. ^ HW Kuhn (1955): The Hungarian method for the assignment problem . Naval Research Logistics Quarterly 2, pp. 83-97.
2. ↑ J. Munkres (1957): Algorithms for the Assignment and Transportation Problems , Journal of the Society of Industrial and Applied Mathematics , Vol. 5 No. 1, pp. 32-38.
3. ↑ WikiHow.com : http://www.wikihow.com/Use-the-Hungarian-Algorithm

literature

• RE Burkard, M. Dell'Amico, S. Martello: Assignment Problems (Revised reprint). SIAM, Philadelphia PA. 2012. ISBN 978-1-611972-22-1
• G. Grosche, V. Ziegler, D. Ziegler (editor): Supplementary chapter to IN Bronstein, KA Semendjajew: Taschenbuch der Mathematik . 6th edition, BSB BG Teubner Verlagsgesellschaft, Leipzig 1990, section 9.1.
• Habr, Jaroslav: The frequency method for solving transport problems and related linear programming problems , in: Wissenschaftliche Zeitung der Universität Dresden 10 (1961), no. 5, pp. 1069-1071.
• Habr, Jaroslav: The Use of Approximation Methods in Linear Programming , in: Proceedings of the IFIP-Congress 62. Amsterdam 1962, pp. 80-82.
• E. Seiffart, K. Manteuffel: Linear optimization . 4th edition, BSB BG Teubner Verlagsgesellschaft, Leipzig 1988, section 4.2.