A New Diagonal Optimal Approach for Assignment Problem

Applied Mathematical Sciences, Vol. 8, 2014, no. 160, 7979 - 7986
HIKARI Ltd, www.m-hikari.com
http://dx.doi.org/10.12988/ams.2014.410796
A New Diagonal Optimal Approach for
Assignment Problem
M. Khalid
Department of Mathematical Sciences
Federal Urdu University of Arts, Sciences & Technology
Karachi-75300, Pakistan
Corresponding Author
Mariam Sultana
Department of Mathematical Sciences
Federal Urdu University, Karachi-75300, Pakistan
Faheem Zaidi
Department of Mathematical Sciences
Federal Urdu University, Karachi-75300, Pakistan
Copyright © 2014 M. Khalid, Mariam Sultana and Faheem Zaidi. This is an open access article
distributed under the Creative Commons Attribution License, which permits unrestricted use,
distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
Different situations give rise to the assignment problem, where we must discover
an optimal way to assign ‘n’ objects to ‘m’ in an bijective function. We have, in
this research, propose the possibility of solving exactly the Linear Assignment
Problem with a method that would be more efficient than the Hungarian method
of exact solution. This method is based on applying a series of pairwise
interchanges of assignments to a starting heuristically generated feasible solution,
wherein each pairwise interchange is guaranteed to improve the objective function
value of the feasible solution.It seems that our algorithm finds the optimal
solution which is the same as one found by the Hungarian method, but in much
simpler.
7980
M. Khalid et al.
Keywords: Assignment Problem; Cost Minimization; Diagonal Sum; Linear
Integral Programming
Introduction
The Assignment method picks a ‘task’ and matches it with the most appropriate
‘agent’, from which the most efficient outcome may be obtained. Since its
introduction in 1952, many different approaches have been developed for finding
best solutions to the assignment problem. A few important ones should be
mentioned: Hungarian Method by Kuhn and Munkres [1, 2] was one of the
earliest ones; linear programming was proposed by Dantzig [3]; the Auction
Algorithm was developed by Bertsekas [4]. Other methods may include one by
Kosowsky and Yuille [5] that uses statistical physics, another by Basirzadh [6]
called Ones Assignment method, which is somewhat similar to the Hungarian and
minimizes or maximizes the objective function,the revised Ones Assignment
Method by Muley and Ghade [7]. Lastly, new improved ones assignment mehod
by authors of this study [8].
This study puts forward and investigates a fresh approach to the solution of the
assignment problem. Looking at it from a research point of view, presenting old
problems in a new framework should be credited because it gives a clear
grounding for comparing different methods. It also helps in the enrichment of the
understanding of dynamics that govern this phenomenon. The assignment
problem is not only an old problem but a very practical one that has given rise to
much theoretical and practical analysis, and that definitely warrants a thorough
investigation.
The Assignment Problem (Mathematical Formulation)
An assignment problem is a bijective mapping of a finite set N  1,2,3,....., n
into itself i.e. permutation  assigning some j  i  to each i  N . The set of all
permutations (assignments) of n items will be denoted by S n and has
n ! elements. Every permutation  of the set N  1,2,3,....., n corresponds
uniquely to a permutation matrix X   x tj  with x ij  1 for j  i  and
x ij  0 for j  i  . Thus, a permutation matrix X  x tj  can be defined as a
matrix which fulfills the following conditions
n

x ij  1 for  j  1,2,3,...., n

x ij  1 for  i  1,2,3,...., n
i 1
n
j1
x ij  0,1 for  i, j  1,2,3,..., n
A new diagonal optimal approach for assignment problem
7981
New Purpose Algorithm
The new algorithm is as follow:
1) Locate the two cells that have minimum cost and next to minimum cost. in
each row, then write their difference (penalty) along the side of the table
against the corresponding row.
2) Locate the two cells that have minimum cost and next to minimum cost in
each column, then write their difference (penalty) below the table against the
corresponding column.
3) Locate the maximum penalty. If it is along the side of the table, make
maximum assignment to the cell having minimum cost in that row. If it is
below the table, make maximum assignment to the cell having minimum cost
in that column. Continue in the same manner until all assignments are made.
4) If the penalties corresponding to two or more rows/columns are equal, find the
difference between first and third minimum value. Identify the maximum
among them and assign the minimum cost among them. This step gives the
initial solution.
Remarks: For finding the optimal solution, we will follow step 5 and 6
5) Write these assigned costs on the top of the column of original assignment
problem. Let a j be the assigned cost for column j . Subtract a j from each
entry of c ij of the corresponding column of assignment matrix
6) Construct a rectangle in such a way that one corner contains negative penalty
and remaining two corners are allocated to the assigned cost values in
corresponding row and column. Calculate the sum of extreme cells of
unassigned diagonal, say d ij . Locate  d ij  0 . Identify the most negative
d ij and exchange the assigned cell of diagonals. Continue the process until all
negative penalties are resolved.
Remarks: If any d ij  0 , then exchange the cells of diagonals at the end.
Numerical Examples
This method is illustrated with some numerical examples.
Example 1: Consider an assignment problem with five jobs assign to five workers
so that the cost is minimized.
W1
W2
W3
W4
W5
J1
J2
J3
J4
J5
11
9
13
21
14
17
7
16
24
10
8
12
15
17
12
16
6
12
28
11
20
15
16
26
13
7982
M. Khalid et al.
By using step 1 and 2, write the difference (penalty) against corresponding row
and column. Identify the maximum penalty. Assign the cell with minimum cost,
as per step 3. Repeat till all values have been assigned.
11
9
13
21
14
17
7
16
24
10
8
12
15
17
12
16
6
12
28
11
20
15
16
26
13
2,
2,
2,
8
3,
6
4,
4,
7
5
2,
3,
4,
10
3,3,3
1
1,2,2,3
4,4,4,5
1,2
All assigned costs are written on the top of the columns of original assignment
matrix. Subtract assigned cost from each entry of the corresponding column of the
assignment matrix. Identify all the negative penalties.
21
10
8
6
16
11
9
13
21
14
17
7
16
24
10
8
12
15
17
12
16
6
12
28
11
20
15
16
26
13
-10 7
-12 -3
-8 6
0 14
-7 0

0
4
7
9
4
10
0
6
22
5
4
-1
0
10
-3
we check the values of d ij by using step 6
d11
-10
0
d 31
-8 0
0 10
0
9
-1
d 22
2
d 51
d 55
0
5
2
d 21
-12 0
0 22
10
0 14
-7 0
7
d 25
0
6
5
-3
0
6
0
0
-3
3
-1
0
A new diagonal optimal approach for assignment problem
7983
After exchange of assigned cells, repeat step 5 and 6 until all negative penalties
are resolved.
11 10 17
6
16
11
9
13
21
14
16
6
12
28
11
20
15
16
26
13
17
7
16
24
10
8
12
15
17
12
0 7 -9 10 4
-2 -3 -5 0 -1
2 6 -2 6 0
10 14 0 22 10
3 0 -5 5 -3

d 13  1 ; d 21  8 ; d 22  2 ; d 23  17
d 25  5 ; d 33  8 ; d 53  9 ; d 55  3
Since, the sum of all unassigned diagonal cells is greater than zero, optimal
solution has been successfully achieved. Hence, the minimum cost will be
Min Cost  11  6  16  17  10  60
Example 2: An assignment problem with six jobs assign to five workers so that
the cost is minimized
W1
W2
W3
W4
W5
J1
J2
J3
J4
J5
J6
12
10
11
6
8
10
18
10
14
12
15
25
3
10
11
22
15
8
13
7
18 8
16 12
15 9
13 12
13 10
By introducing dummy variable and follow steps 1 to 3, gives us
12
10
11
6
8
0
10
18
10
14
12
0
15
25
3
10
11
0
6,
2,
2,
4
10,
0,
2,
4,
8
3,
7
22
15
8
13
7
0
18 8
16 12
15 9
13 12
13 10
0 0
7, 13
1,
6(8)
8,
1,
2,
4,
4
2,2,2,2,2
2,2,2,2,6
5,5
4,4,6(7),6
1,1,1
0
7984
M. Khalid et al.
Steps 1 - 4 get an initial feasible solution.Steps 5&6 iterate from a feasible
solution to an optimal solution, stopping when all d (i, j) are non-negative.
Following step 5, we have
6
10
3
7
12
10
11
6
8
0
10
18
10
14
12
0
15 22 18 8
25 15 16 12
3 8 15 9
10 13 13 12
11 7 13 10
0 0 0 0
d 56
8 0
0 -2
d 61
0 13
-6 0
0
12
6
7
d 64
6 0 12 15 18 -4
4 8 22 8 16 0
5 0
0 1 15 -3
0 4
7 6 13 0
2 2
8 0 13 -2
-6 -10 -3 -7 0 -12

d 36
22 0
0 -3
19
d16
0
8
d 63
0 15
-3 0
12
d 62
0 18
-10 0
0 13
-7 0
d 66
6
16 0
0 -12
Here,  d ij  0 , therefore an optimal solution has been achieved.
Min Cost  10  12  3  6  7  0  38
Example 3: Consider an assignment problem with 6  6 matrix.
W1
W2
W3
W4
W5
W6
J1
J2
J3
J4
J5
J6
41
22
27
45
29
82
72
29
39
50
40
40
39
49
60
48
39
40
52
65
51
52
26
60
25
81
32
37
30
51
51
50
32
43
33
30
Applying, new proposed algorithm on it, we have
4
-4
0
4
8
A new diagonal optimal approach for assignment problem
41
22
27
45
29
82
72
29
39
50
40
40
5,
10,
5,
10,
5, 10(11)
18
7985
39
49
60
48
39
40
52
65
51
52
26
60
25
81
32
37
30
51
51
14,14
50
7,7,7
32
5,5,5,5
43
6,6,2,2
33
3
30 10,10,10(10),10
0,
1,
8,
8,
8
25
5,
7
2,
2,
2,
2,
13
Step 5 yields
27 29 48 26 25 30
41
22
27
45
29
82
72
29
39
50
40
40
39
49
60
48
39
40
52
65
51
52
26
60
25
81
32
37
30
51
51
50
32
43
33
30
14
-5
0
18
2
55

43
0
10
21
11
11
-9
1
12
0
-9
-8
26 0 21
39 56 20
25 7 2
26 12 13
0 5 3
34 26 0
Calculating the value of d ij
d13
d 53
-9 0
0 12
0 26
-9 0
3
17
d 21
-5 0
0 10
d 63
0 13
-8 0
5
5
Since,  d ij  0 , we get an optimal solution. the minimum cost of this assignment
matrix is Min Cost  27  29  48  26  25  30  185
Conclusion
The Assignment problem revolves around the prospect of discovery of one-to-one
matching between a pair of sets, which is optimal. A new algorithm has been
7986
M. Khalid et al.
proposed in this paper to achieve an exact optimal solution of an assignment
problem. There is a vast difference between previously reported algorithm and
this new one. Even with an addition of a few new features, the new method is
efficient and fast, and can replace old algorithms wherever they have been used.
Acknowledgements. The authors would like to thank the reviewers for the
comments which led to an improvement in the paper. Special thanks to Ms.
Wishaal Khalid for proof reading.
References
[1] H. Kuhn, The Hungarian Method for the Assignment Problem, Naval
Research Logistics Quarterly, 2 (1955), 83 - 97.
http://dx.doi.org/10.1002/nav.3800020109
[2] J. Munkres, Algorithms for the Assignment and Transportation Problems,
Journal of the Society of Industrial and Applied Mathematics, 5 (1957), 32 - 38.
http://dx.doi.org/10.1137/0105003
[3] G. B. Dantzig and M. N. Thapa, Linear Programming: Theory and
extensions, Springer, 1997.
[4] D. P. Bertsekas, Auction Algorithms for Network Flow Problems: A Tutorial
Introduction, Computational Optimization and Applications, 1 (1992), 7 - 66.
http://dx.doi.org/10.1007/bf00247653
[5] J. Kosowsky and A. Yuille, Solving the Assignment Problem with Statistical
Physics, IEEE, 1991. http://dx.doi.org/10.1109/ijcnn.1991.155168
[6] H. Basirzadeh, Ones Assignment Method for solving assignment problems,
Applied Mathematical Sciences, l (2012), 2345 - 2355.
[7] K. P. Ghadle and Y. M. Muley, Revised Ones Assignment Method for
solving assignment problem. Journal of Statistics and Mathematics, 4 (2013),
147-150.
[8] M. Khalid, Mariam Sultana and Faheem Zaidi, “New Improved Ones
Assignment Method Applied Mathematical Sciences, Vol. 8, 2014, no. 84, 4171 –
4177. http://dx.doi.org/10.12988/ams.2014.45327
Received: October 10, 2014; Published: November 18, 2014