Munkres Algorithm For The Assignment Problem

Munkres' Assignment Algorithm
Modified for Rectangular Matrices

Notice: This page has been updated.  Earlier version is here.

Assignment Problem - Let C be an nxn matrix representing the costs of each of n workers to perform any of n jobs.  The assignment problem is to assign jobs to workers so as to minimize the total cost. Since each worker can perform only one job and each job can be assigned to only one worker the assignments constitute an independent set of the matrix C.

An arbitrary assignment is shown above in which worker a is assigned job q, worker b is assigned job s and so on.  The total cost of this assignment is 23.  Can you find a lower cost assignment? Can you find the minimal cost assignment? Remember that each assignment must be unique in its row and column.

A brute-force algorithm for solving the assignment problem involves generating all independent sets of the matrix C, computing the total costs of each assignment and a search of all assignment to find a minimal-sum independent set. The complexity of this method is driven by the number of independent assignments possible in an nxn matrix. There are n choices for the first assignment, n-1 choices for the second assignment and so on, giving n! possible assignment sets. Therefore, this approach has, at least, an exponential runtime complexity.

As each assignment is chosen that row and column are eliminated from consideration.  The question is raised as to whether there is a better algorithm.  In fact there exists a polynomial runtime complexity algorithm for solving the assignment problem developed by James Munkre's in the late 1950's despite the fact that some references still describe this as a problem of exponential complexity.

The following 6-step algorithm is a modified form of the original Munkres' Assignment Algorithm (sometimes referred to as the Hungarian Algorithm).  This algorithm describes to the manual manipulation of a two-dimensional matrix by starring and priming zeros and by covering and uncovering rows and columns.  This is because, at the time of publication (1957), few people had access to a computer and the algorithm was exercised by hand.
 

Step 0:  Create an nxm  matrix called the cost matrix in which each element represents the cost of assigning one of n workers to one of m jobs.  Rotate the matrix so that there are at least as many columns as rows and let k=min(n,m).

Step 1:  For each row of the matrix, find the smallest element and subtract it from every element in its row.  Go to Step 2.

Step 2:  Find a zero (Z) in the resulting matrix.  If there is no starred zero in its row or column, star Z. Repeat for each element in the matrix. Go to Step 3.

Step 3:  Cover each column containing a starred zero.  If K columns are covered, the starred zeros describe a complete set of unique assignments.  In this case, Go to DONE, otherwise, Go to Step 4.

Step 4:  Find a noncovered zero and prime it.  If there is no starred zero in the row containing this primed zero, Go to Step 5.  Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6.

Step 5:  Construct a series of alternating primed and starred zeros as follows.  Let Z0 represent the uncovered primed zero found in Step 4.  Let Z1 denote the starred zero in the column of Z0 (if any). Let Z2 denote the primed zero in the row of Z1 (there will always be one).  Continue until the series terminates at a primed zero that has no starred zero in its column.  Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix.  Return to Step 3.

Step 6:  Add the value found in Step 4 to every element of each covered row, and subtract it from every element of each uncovered column.  Return to Step 4 without altering any stars, primes, or covered lines.

DONE:  Assignment pairs are indicated by the positions of the starred zeros in the cost matrix.  If C(i,j) is a starred zero, then the element associated with row i is assigned to the element associated with column j.

Some of these descriptions require careful interpretation.  In Step 4, for example, the possible situations are, that there is a noncovered zero which get primed and if there is no starred zero in its row the program goes onto Step 5.  The other possible way out of Step 4 is that there are no noncovered zeros at all, in which case the program goes to Step 6.
 

At first it may seem that the erratic nature of this algorithm would make its implementation difficult.  However, we can apply a few general rules of programming style to simplify this problem.  The same rules can be applied to any step-algorithm.

Good Programming Style and Design Practices

1. Strive to create readable source code through the use of blank lines, comments and spacing.

2. Use consistent naming conventions, for variable and constant identifiers and subprograms.

3. Use consistent indentation and always indent the bodies of conditionals and looping constructs.

4. Place logically distinct computations in their own execution blocks or in separate subprograms.

5. Don't use global variables inside subprograms except where such use is clear and improves readability and efficiency.

6. Use local variables where appropriate and try to limit the creation of unnecessary identifiers in the main program.

7. Open I/O files only when needed and close them as soon as they are no longer required.

8. Work to keep the level of nesting of conditionals and loops at a minimum.

9. Use constant identifiers instead of hardwiring for-loop and array ranges in the body of the code with literal values.

10. When you feel that things are getting out of control, start over. Re-coding is good coding.

An Implementation of Munkres' Assignment Algorithm


By applying Rule 4 to the step-algorithm we decide to make each step its own procedure.  Now we can apply Rule 8 by using a case statement in a loop to control the ordering of step execution.  The main loop for Munkres as a step-wise algorithm is shown here implemented in C#.



In each pass of the loop the step procedure called sets the value of step for the next pass.  When the algorithm is finished the value of step is set to some value outside the range 1..7 so that done will be set to true and the program will end.  In the completed program the tagged (starred) zeros flag the row/column pairs that have been assigned to each other.  We will discuss the implementation of a procedure for each step of Munkres' Algorithm below. We will assume that the cost matrix C(i,j) has already been loaded with the first index referring to the row number and the second index referring to the column number.

Step 1

For each row of the matrix, find the smallest element and subtract it from every element in its row.  Go to Step 2. We can define a local variable called minval that is used to hold the smallest value in a row.  Notice that there are two loops over the index j appearing inside an outer loop over the index i. The first inner loop over the index j searches a row for the minval.  Once minval has been found this value is subtracted from each element of that row in the second inner loop over j.  The value of step is set to 2 just before stepone ends.


Step 2

Find a zero (Z) in the resulting matrix.  If there is no starred zero in its row or column, star Z. Repeat for each element in the matrix. Go to Step 3.  In this step, we introduce the mask matrix M, which in the same dimensions as the cost matrix and is used to star and prime zeros of the cost matrix.  If M(i,j)=1 then C(i,j) is a starred zero,  If M(i,j)=2 then C(i,j) is a primed zero.  We also define two vectors R_cov and C_cov that are used to "cover" the rows and columns of the cost matrix C.  In the nested loop (over indices i and j) we check to see if C(i,j) is a zero value and if its column or row is not already covered.  If not then we star this zero (i.e. set M(i,j)=1) and cover its row and column (i.e. set R_cov(i)=1 and C_cov(j)=1).  Before we go on to Step 3, we uncover all rows and columns so that we can use the cover vectors to help us count the number of starred zeros.


Step 3

Cover each column containing a starred zero.  If K columns are covered, the starred zeros describe a complete set of unique assignments.  In this case, Go to DONE, otherwise, Go to Step 4. Once we have searched the entire cost matrix, we count the number of independent zeros found.  If we have found (and starred) K independent zeros then we are done.  If not we procede to Step 4.


Step 4

Find a noncovered zero and prime it.  If there is no starred zero in the row containing this primed zero, Go to Step 5.  Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6.


In this step, statements such as "find a noncovered zero" are clearly distinct operations that deserve their own functional blocks.  We have decomposed this step into a main method and three subprograms (2 methods and a boolean function).


Step 5

Construct a series of alternating primed and starred zeros as follows.  Let Z0 represent the uncovered primed zero found in Step 4.  Let Z1 denote the starred zero in the column of Z0 (if any). Let Z2 denote the primed zero in the row of Z1 (there will always be one).  Continue until the series terminates at a primed zero that has no starred zero in its column.  Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix.  Return to Step 3.  You may notice that Step 5 seems vaguely familiar.  It is a verbal description of the augmenting path algorithm (for solving the maximal matching problem) which we discussed in Lecture 3.  We decompose the operations of this step into a main procedure and five relatively simple subprograms.



As with the previous step we have decomposed Step 5 into a number of separate methods each performing a functionally distinct task corresponding to the description in Munkres algorithm.


Step 6

Add the value found in Step 4 to every element of each covered row, and subtract it from every element of each uncovered column.  Return to Step 4 without altering any stars, primes, or covered lines. Notice that this step uses the smallest uncovered value in the cost matrix to modify the matrix.  Even though this step refers to the value being found in Step 4 it is more convenient to wait until you reach Step 6 before searching for this value.  It may seem that since the values in the cost matrix are being altered, we would lose sight of the original problem.  However, we are only changing certain values that have already been tested and found not to be elements of the minimal assignment.  Also we are only changing the values by an amount equal to the smallest value in the cost matrix, so we will not jump over the optimal (i.e. minimal assignment) with this change.


  For Step 6, there is one supporting method to find the smallest uncovered value (described in Step 4).


Thecode used above is available in a complete Microsoft Visual Studio .NET 2010 C# project - munkres.zip.  This is a console application that can read a text-file containing the cost matrix values arranged in a two-dimensional array or generate test matrices.  The input file should be placed in the same folder as the calling executable.  This project application can generate a random value cost matrix or a worst-case test matrix C(i,j) = i*j.  Setting the value of each element C(i,j) of the cost matrix to the value i*j ensures that the maximum number of operations will be required to find the minimal assignment (which is the back diagonal).  The locations of the ones (1's) in the associated mask matrix M correspond to the assignment pairs selected by Munkres' Algorithm.  The following is an example run of the algorithm on a 3x3 worst-case test matrix.

An Example Execution of Munkres' Algorithm

This example illustrates the method of implementing a step-algorithm.  It also serves to demonstrate why we do not attempt to implement every algorithm discussed in this course. :-)

Answers to Frequently Asked Questions

  1. The algorthm will work even when the minimum values in two or more rows are in the same column.
  2. The algorithm will work even when two or more of the rows contain the same values in the the same order.
  3. The algorithm will work even when all the values are the same (although the result is not very interesting).
  4. Munkres Assignment Algorithm is not exponential run time or intractable; Munkres can achieve a low order polynomial run time, worst-case O(n3). see doi: 10.1007/BF01930994
  5. Optimality is guaranteed in Munkres Assignment Algorithm.
  6. Setting the cost matrix to C(i,j) = i*j  makes a good testing matrix for this problem.
  7. In this algorithm the range of indices is[0..n-1] rather than [1..n].
  8. Step 3 is an example of the greedy method.  If the minimum values are all in different rows then their positions represent the minimal pairwise assignments.
  9. Step 5 is an example of the Augmenting Path Algorithm (Stable Marriage Problem).
  10. Step 6 is an example of constraint relaxation.  It is "giving up" on a particular cost and raising the constraint by the least amount possible.
  11. If your implementation is jumping between Step 4 and Step 6 without entering Step 5, you probably have not properly dealt with recognizing that there are no uncovered zeros in Step 4.
  12. In the matrix M 1=starred zero and 2=primed zero.  So, if C[i,j] is a starred zero we would set M[i,j]=1.  All other elements in M are set to zero
  13. The Munkres assignment algorithm can be implemented as a sparse matrix, but you will need to ensure that the correct (optimal) assignment pairs are active in the sparse cost matrix C
  14. Munkres Assignment can be applied to TSP, pattern matching, track initiation, data correlation, and (of course) any pairwise assignment application.
  15. Munkres can be extended to rectangular arrays (i.e. more jobs than workers, or more workers than jobs) .
  16. The best way to find a maximal assignment is to replace the values ci,j in the cost matrix with C[i,j] = bigval - ci,j.
  17. Original Reference:  Algorithms for Assignment and Transportation Problems, James Munkres, Journal of the Society for Industrial and Applied Mathematics Volume 5, Number 1, March, 1957
  18. Extension to Rectangular Arrays Ref:  F. Burgeois and J.-C. Lasalle. An extension of the Munkres algorithm for the assignment problem to rectangular matrices. Communications of the ACM, 142302-806, 1971.

The Hungarian method is a combinatorial optimizationalgorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.[1][2]

James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial.[3] Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was , however Edmonds and Karp, and independently Tomizawa noticed that it can be modified to achieve an running time. Ford and Fulkerson extended the method to general transportation problems.[citation needed] In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.[4]

Simple explanation of the assignment problem[edit]

In this simple example there are three workers: Armond, Francine, and Herbert. One of them has to clean the bathroom, another sweep the floors and the third washes the windows, but they each demand different pay for the various tasks. The problem is to find the lowest-cost way to assign the jobs. The problem can be represented in a matrix of the costs of the workers doing the jobs. For example:

Clean bathroomSweep floorsWash windows
Armond$2$3$3
Francine$3$2$3
Herbert$3$3$2

The Hungarian method, when applied to the above table, would give the minimum cost: this is $6, achieved by having Armond clean the bathroom, Francine sweep the floors, and Herbert wash the windows.

Setting[edit]

We are given a nonnegative n×nmatrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th job to the i-th worker. We have to find an assignment of the jobs to the workers that has minimum cost. If the goal is to find the assignment that yields the maximum cost, the problem can be altered to fit the setting by replacing each cost with the maximum cost subtracted by the cost.

The algorithm is easier to describe if we formulate the problem using a bipartite graph. We have a complete bipartite graph with worker vertices () and job vertices (), and each edge has a nonnegative cost . We want to find a perfect matching with minimum cost.

Let us call a function a potential if for each . The value of potential is . It can be seen that the cost of each perfect matching is at least the value of each potential. The Hungarian method finds a perfect matching and a potential with equal cost/value which proves the optimality of both. In fact it finds a perfect matching of tight edges: an edge is called tight for a potential if . Let us denote the subgraph of tight edges by . The cost of a perfect matching in (if there is one) equals the value of .

The algorithm in terms of bipartite graphs[edit]

During the algorithm we maintain a potential y and an orientation of (denoted by ) which has the property that the edges oriented from T to S form a matching M. Initially, y is 0 everywhere, and all edges are oriented from S to T (so M is empty). In each step, either we modify y so that its value increases, or modify the orientation to obtain a matching with more edges. We maintain the invariant that all the edges of M are tight. We are done if M is a perfect matching.

In a general step, let and be the vertices not covered by M (so consists of the vertices in S with no incoming edge and consists of the vertices in T with no outgoing edge). Let be the set of vertices reachable in from by a directed path only following edges that are tight. This can be computed by breadth-first search.

If is nonempty, then reverse the orientation of a directed path in from to . Thus the size of the corresponding matching increases by 1.

If is empty, then let . is positive because there are no tight edges between and . Increase y by on the vertices of and decrease y by on the vertices of . The resulting y is still a potential. The graph changes, but it still contains M. We orient the new edges from S to T. By the definition of the set Z of vertices reachable from increases (note that the number of tight edges does not necessarily increase).

We repeat these steps until M is a perfect matching, in which case it gives a minimum cost assignment. The running time of this version of the method is : M is augmented n times, and in a phase where M is unchanged, there are at most n potential changes (since Z increases every time). The time needed for a potential change is .

Matrix interpretation[edit]

Given workers and tasks, and an n×n matrix containing the cost of assigning each worker to a task, find the cost minimizing assignment.

First the problem is written in the form of a matrix as given below

a1a2a3a4
b1b2b3b4
c1c2c3c4
d1d2d3d4

where a, b, c and d are the workers who have to perform tasks 1, 2, 3 and 4. a1, a2, a3, a4 denote the penalties incurred when worker "a" does task 1, 2, 3, 4 respectively. The same holds true for the other symbols as well. The matrix is square, so each worker can perform only one task.

Step 1

Then we perform row operations on the matrix. To do this, the lowest of all ai (i belonging to 1-4) is taken and is subtracted from each element in that row. This will lead to at least one zero in that row (We get multiple zeros when there are two equal elements which also happen to be the lowest in that row). This procedure is repeated for all rows. We now have a matrix with at least one zero per row. Now we try to assign tasks to agents such that each agent is doing only one task and the penalty incurred in each case is zero. This is illustrated below.

0a2'a3'a4'
b1'b2'b3'0
c1'0c3'c4'
d1'd2'0d4'

The zeros that are indicated as 0' are the assigned tasks.

Step 2

Sometimes it may turn out that the matrix at this stage cannot be used for assigning, as is the case for the matrix below.

0a2'a3'a4'
b1'b2'b3'0
0c2'c3'c4'
d1'0d3'd4'

In the above case, no assignment can be made. Note that task 1 is done efficiently by both agent a and c. Both can't be assigned the same task. Also note that no one does task 3 efficiently. To overcome this, we repeat the above procedure for all columns (i.e. the minimum element in each column is subtracted from all the elements in that column) and then check if an assignment is possible.

In most situations this will give the result, but if it is still not possible then we need to keep going.

Step 3

All zeros in the matrix must be covered by marking as few rows and/or columns as possible. The following procedure is one way to accomplish this:

First, assign as many tasks as possible.

  • Row 1 has one zero, so it is assigned. The 0 in row 3 is crossed out because it is in the same column.
  • Row 2 has one zero, so it is assigned.
  • Row 3's only zero has been crossed out, so nothing is assigned.
  • Row 4 has two uncrossed zeros. Either one can be assigned (both are optimum), and the other zero would be crossed out.

Alternatively, the 0 in row 3 may be assigned, causing the 0 in row 1 to be crossed instead.

0'a2'a3'a4'
b1'b2'b3'0'
0c2'c3'c4'
d1'0'0d4'

Now to the drawing part.

  • Mark all rows having no assignments (row 3).
  • Mark all (unmarked) columns having zeros in newly marked row(s) (column 1).
  • Mark all rows having assignments in newly marked columns (row 1).
  • Repeat for all non-assigned rows.
×
0'a2'a3'a4'×
b1'b2'b3'0'
0c2'c3'c4'×
d1'0'0d4'

Now draw lines through all marked columns and unmarked rows.

×
0'a2'a3'a4'×
b1'b2'b3'0'
0c2'c3'c4'×
d1'0'0d4'

The aforementioned detailed description is just one way to draw the minimum number of lines to cover all the 0s. Other methods work as well.

Step 4

From the elements that are left, find the lowest value. Subtract this from every unmarked element and add it to every element covered by two lines.

Repeat steps 3–4 until an assignment is possible; this is when the minimum number of lines used to cover all the 0s is equal to max(number of people, number of assignments), assuming dummy variables (usually the max cost) are used to fill in when the number of people is greater than the number of assignments.

Basically you find the second minimum cost among the remaining choices. The procedure is repeated until you are able to distinguish among the workers in terms of least cost.

Bibliography[edit]

  • R.E. Burkard, M. Dell'Amico, S. Martello: Assignment Problems (Revised reprint). SIAM, Philadelphia (PA.) 2012. ISBN 978-1-61197-222-1
  • M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995.
  • R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993.
  • S. Martello, "Jeno Egerváry: from the origins of the Hungarian algorithm to satellite communication". Central European Journal of Operations Research 18, 47–58, 2010

References[edit]

External links[edit]

  • Bruff, Derek, "The Assignment Problem and the Hungarian Method", [1]
  • Mordecai J. Golin, Bipartite Matching and the Hungarian Method, Course Notes, Hong Kong University of Science and Technology.
  • R. A. Pilgrim, Munkres' Assignment Algorithm. Modified for Rectangular Matrices, Course notes, Murray State University.
  • Mike Dawes, The Optimal Assignment Problem, Course notes, University of Western Ontario.
  • On Kuhn's Hungarian Method – A tribute from Hungary, András Frank, Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
  • Lecture: Fundamentals of Operations Research - Assignment Problem - Hungarian Algorithm, Prof. G. Srinivasan, Department of Management Studies, IIT Madras.
  • Extension: Assignment sensitivity analysis (with O(n^4) time complexity), Liu, Shell.
  • Solve any Assignment Problem online, provides a step by step explanation of the Hungarian Algorithm.
  1. ^Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.
  2. ^Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253–258, 1956.
  3. ^J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
  4. ^http://www.lix.polytechnique.fr/~ollivier/JACOBI/jacobiEngl.htm

0 Replies to “Munkres Algorithm For The Assignment Problem”

Lascia un Commento

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *