LAB 5: ASSIGNMENT PROBLEMS AND SPARSE MATRICES

Mathematics:

The assignment problem is to assign tasks to facilities on a one-to-one basis in an optimal way. An example of the assignment problem is to assign n workers to n jobs such that the total cost (e.g. the costs of training, qualification-dependent salaries, etc.) is minimized. There are exactly n! = n*(n-1)*(n-2)*…*3*2*1 ways to assign n workers to n jobs. Costs of all n! combinations can be checked and the minimal cost can be found. However, such algorithm is computational inefficient, since the number of combinations grows fast with larger n, e.g. 10! = 3,628,800. Two Hungarian mathematicians, D. Konig and E. Egervary, proposed a better algorithm called the Hungarian method. This project exploits a simple computational method to approach to the optimal solution. (The Hungarian method would be the best solution but it is much more difficult to code).

Let us define the n-by-n cost matrix C and the n-by-n assignment matrix X:

C = ,     X =

Here ci,j is the cost of assigning the i-th worker to the j-th job (in \$) and xi,j is assignment, such that xi,j = 1 if the i-th worker is assigned to the j-th job, and xi,j = 0, otherwise. The assignment is one-to-one if the matrix X has no two ones in the same row or in the same column. The cost of the current assignment is

z = ci,j xi,j

We will be working with the following problem: assign n = 9 candidates to n=9 jobs to minimize the total salary cost paid by the department. The individual salaries of each candidate at each job position depend on their qualification and are given by the cost matrix (in \$ per hour):

 Sam Jill John Liz Ann Lois Pete Alex Herb Administrator 20 15 10 10 17 23 25 5 15 Secretary to the Chair 10 10 12 15 9 7 8 7 8 Undergraduate Secretary 12 9 9 10 10 5 7 13 9 Graduate Secretary 13 14 10 15 15 5 8 20 10 Financial Clerk 12 13 10 15 14 5 9 20 10 Secretary 15 14 15 16 15 5 10 20 10 Web designer 7 9 12 12 7 6 7 15 12 Receptionist 5 6 8 8 5 4 5 10 7 Typist 5 6 8 8 5 4 5 10 7

If we start with the position of Administrator and assign it to Alex (he gets the minimal salary for this position), then we assign the position of Secretary to Chair to Lois (he gets the minimal salary for this position), and so on, up to the position of Typist, then the assignment is given by the assignment matrix:

X =   0     0     0     0     0     0     0     1     0

0     0     0     0     0     1     0     0     0

0     0     0     0     0     0     1     0     0

0     0     1     0     0     0     0     0     0

0     0     0     0     0     0     0     0     1

0     1     0     0     0     0     0     0     0

1     0     0     0     0     0     0     0     0

0     0     0     0     1     0     0     0     0

0     0     0     1     0     0     0     0     0

where the total cost z = 73. The optimal assignment is however different from the first-to-assign solution above. The optimal assignment is:

X =  0      0      0     0      0     0      0      1     0

0     0     0     0     0     0     0     0     1

0     0     0     1     0     0     0     0     0

0     0     0     0     0     0     1     0     0

0     0     1     0     0     0     0     0     0

0     0     0     0     0     1     0     0     0

0     0     0     0     1     0     0     0     0

1     0     0     0     0     0     0     0     0

0     1     0     0     0     0     0     0     0

where the total minimal cost z* = 64.

Objectives:

·         understand computational algorithms for solving the assignment problems

·         code the computational algorithms by using MATLAB programming constructions

·         exploit the algorithms for different assignment problems

#### MATLAB script for solving the assignment problem by checking costs of all possible assignments

Steps of the computational algorithm:

1. Input the cost matrix C and find the size of the matrix.
2. Construct all possible permutations of n numbers (n! combinations). Use function "perms" to build a n!-by-n matrix of permutations.
3. For each row of the permutation matrix:

a)      Build up the assignment matrix X from a zero n-by-n matrix by assigning 1 row-by-row to the columns of the permutation matrix.

b)      Compute the total cost z of the assignment. Use function "sum" to compute z.

1. Find the assignment with the minimal cost and display the cost z* and the assignment matrix X.

#### MATLAB script for solving the assignment problem by approaching to the optimal solution

Steps of the computational algorithm:

1. Build up the assignment matrix X from a zero n-by-n matrix by assigning 1 row-by-row to the column, where the cost is minimal compared to costs in other columns of the given row. If the minimal cost occurs in the column that has already the 1-assigned position in the rows above the given row, take the column with the second minimal cost, and so on.

a)      Organize a single loop for rows of matrix X.

b)      Use MATLAB function "sort" with two output arguments (for the value and for its index in the row) to sort costs in the ascending order.

c)      Organize another loop for elements of the sorted vector in the ascending order.

d)      Use MATLAB function "any" to check if the selected column has already non-zero values.

1. Consider two 1-assigned positions at (i1,j1) and (i2,j2). This assignment has the cost: ci1,j1 + ci2,j2. If the workers would interchange with their jobs, the new cost would be: ci1,j2 + ci2,j1. After the interchange, he new assignment is more optimal if the difference in costs is negative, i.e. Dz = ci1,j2 + ci2,j1 - ci1,j1 - ci2,j2 < 0.

1. Starting with the given assignment matrix X, loop through all rows of X making exchange of 1-assigned positions, if necessary.

e)      For each row, compute the difference in costs that would result if the current 1-assigned position interchanges with the position in the other (n-1) column. You should compute (n-1) numbers for each row.

f)       Use functions "find" and "min".

g)      If all numbers are positive or zero, move to the next row.

h)      If there exists a negative value for Dz, select the minimal value of Dz and make the interchange of 1-s and 0-s in the corresponding positions in the assignment matrix X.

i)        Compute the total cost of the new assignment.

1. If there were negative entries Dz in step (2), proceed with step (4) again. If all entries Dz were positive or zero, stop the algorithm and compute the total minimal cost z of the found assignment matrix X.

1. The computational algorithm will stop in a finite number of iterations, where the minimal cost solution is reached. However, your solution may not be optimal yet, but very close to the optimal solution. In general algorithm, step (3) has to be modified since more complicated exchanges of assignments (involving three and more interchanges at the same time) may still result in the decrease of the total cost. Compare the minimal cost solution obtained in the second script with the optimal solution obtained in the first script in this laboratory.

Quiz:

1. Modify the scripts by using the function "sparse" for sparse assignment matrix X.
2. Find the optimal assignment for the following cost matrices:

(a)    (b)    (c)