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.
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).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.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.
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.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.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.
procedure munkres isIn each pass of the loop the step procedure called sets the value of stepnum for the next pass. When the algorithm is finished the value of stepnum is set to some value outside the range 1..6 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.
n : constant integer := 20; -- num rows/columns (this version is hard-wired for square matrices)
C : is array(1..n,1..n) of float; -- cost matrix
M : is array(1..n,1..n) of integer; -- a mask matrix to indicate primed (= 2) and starred (=1) zeros in C
Row,Col : is array(1..n) of integer; -- maintains record of which row/columns are covered.
stepnum : integer; -- covered = 1, non-covered = 0
done : boolean;function step1(stepnum: in out integer) is
:
function step2(stepnum: in out integer) is
:
function step3(stepnum: in out integer) is
:begin
done:=false;
stepnum:=1;
while not(done) loop
case stepnum is
when 1 => step1(stepnum);
when 2 => step2(stepnum);
when 3 => step3(stepnum);
when 4 => step4(stepnum);
when 5 => step5(stepnum);
when 6 => step6(stepnum);
when others => done:=true;
end case;
end loop;
end munkres;
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.
procedure stepone(step : in out
integer) is
minval : integer;
begin
for i
in 1..n loop
minval:=C(i,1);
for j in 2..n
loop
if
minval>C(i,j) then
minval:=C(i,j);
end
if;
end loop;
for j in 1..n
loop
C(i,j):=C(i,j)-minval;
end
loop;
end loop;
step:=2;
end stepone;
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.
procedure steptwo(step: in out integer)
is
begin
for i in 1..n loop
for j in 1..n
loop
if
C(i,j)=0 and C_cov(j)=0 and R_cov(i)=0 then
M(i,j):=1;
C_cov(j):=1;
R_cov(i):=1;
end if;
end loop;
end loop;
for i in 1..n loop
C_cov(i):=0;
R_cov(i):=0;
end loop;
step:=3;
end steptwo;
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.
procedure stepthree(step : in out integer)
is
count : integer;
begin
for i in 1..n
loop
for j in
1..n loop
if M(i,j)=1 then
C_cov(j):=1;
end if;
end loop;
end loop;
count:=0;
for j in 1..n
loop
count:=count +
C_cov(j);
end loop;
if count>=n then
step:=7;
else
step:=4;
end if;
end
stepthree;
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 procedure and three subprograms (2 procedures and a boolean function).
procedure stepfour(step : in out
integer) is
row,col : integer;
done : boolean;
procedure find_a_zero(row,col : out
integer) is
i,j :
integer;
done: boolean;
begin
row:=0;
col:=0;
i:=1;
done:=false;
loop
j:=1;
loop
if C(i,j)=0
and R_cov(i)=0 and C_cov(j)=0 then
row:=i;
col:=j;
done:=true;
end
if;
j:=j+1;
exit
when j>n;
end
loop;
i:=i+1;
if i>n then
done:=true; end if;
exit when done;
end loop;
end find_a_zero;
function star_in_row(row : integer)
return boolean is
tbool :
boolean;
begin
tbool:=false;
for j in 1..n
loop
if
M(row,j)=1 then
tbool:=true;
end if;
end loop;
return tbool;
end star_in_row;
procedure find_star_in_row(row, col : in
out integer) is
begin
col:=0;
for j in 1..n
loop
if
M(row,j)=1 then
col:=j;
end if;
end loop;
end find_star_in_row;
begin
done:=false;
while not(done) loop
find_a_zero(row,col);
if row=0 then
done:=true;
step:=6;
else
M(row,col):=2;
if star_in_row(row)
then
find_star_in_row(row,col);
R_cov(row):=1;
C_cov(col):=0;
else
done:=true;
step:=5;
Z0_r:=row;
Z0_c:=col;
end
if;
end if;
end loop;
end
stepfour;
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.
procedure stepfive(step : in out
integer) is
count : integer;
done : boolean;
r,c : integer;
procedure find_star_in_col(c : in integer; r : in
out integer) is
begin
r:=0;
for i
in 1..n loop
if
M(i,c)=1 then
r:=i;
end if;
end loop;
end
find_star_in_col;
procedure find_prime_in_row(r : in integer; c :
in out integer) is
begin
for j in 1..n loop
if M(r,j)=2 then
c:=j;
end if;
end loop;
end
find_prime_in_row;
procedure convert_path is
begin
for i in 1..count
loop
if
M(path(i,1),path(i,2))=1 then
M(path(i,1),path(i,2)):=0;
else
M(path(i,1),path(i,2)):=1;
end
if;
end loop;
end convert_path;
procedure clear_covers is
begin
for i in 1..n
loop
R_cov(i):=0;
C_cov(i):=0;
end loop;
end
clear_covers;
procedure erase_primes is
begin
for i in 1..n
loop
for j in
1..n loop
if M(i,j)=2 then
M(i,j):=0;
end if;
end loop;
end loop;
end
erase_primes;
begin
count:=1;
path(count,1):=z0_r;
path(count,2):=z0_c;
done:=false;
while not(done) loop
find_star_in_col(path(count,2),r);
if r>0 then
count:=count+1;
path(count,1):=r;
path(count,2):=path(count-1,2);
else
done:=true;
end if;
if not(done)
then
find_prime_in_row(path(count,1),c);
count:=count+1;
path(count,1):=path(count-1,1);
path(count,2):=c;
end if;
end loop;
convert_path;
clear_covers;
erase_primes;
step:=3;
end stepfive;
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.
procedure stepsix(step : in out integer)
is
minval : integer;
procedure find_smallest(minval : out
integer) is
begin
minval:=integer'last;
for i in 1..n
loop
for j
in 1..n loop
if R_cov(i)=0
and C_cov(j)=0 then
if
minval>C(i,j) then
minval:=C(i,j);
end
if;
end
if;
end
loop;
end loop;
end find_smallest;
begin
find_smallest(minval);
for i in
1..n loop
for j
in 1..n loop
if R_cov(i)=1
then
C(i,j):=C(i,j)+minval;
end if;
if
C_cov(j)=0 then
C(i,j):=C(i,j)-minval;
end if;
end loop;
end loop;
step:=4;
end stepsix;
An Example Execution of Munkres' Algorithm
Jobs = {p, q, r} Cost of assigning job j to work i is
|
1. Step 0 |
2. Step 1 |
3. Step 2 |
4. Step 3 |
5. Step 4 |
6. Step 6 |
7. Step 4 |
8. Step 5 |
9. Step 3 |
10. Step 4 |
11. Step 6 |
12. Step 4 |
13. Step 6 |
14. Step 4 |
15. Step 5 |
16. Step 3 |
17. Done |
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