Revisiting assignment problem: A novel approach to optimality
Abstract
Known since decades, all pursue standard algorithm to arrive at optimal basic feasible solution of assignment problem. Retaining the prime objective of assignment, we like to share what our approaches are that initially searches for a basic feasible solution and attempts to rectify each allocation to its optimal value. We, strongly, are of the opinion that this novel approach possesses logical but faster proceedings to optimality: once on achieving basic feasible solution. We are of the opinion that this new approach, on the basis of its own merits, will be widely accepted in the academic world of the subject.
Full Text
Tables and figures are in the full-text PDF.
Introduction
This section narrates some salient features of Hungarian algorithm which targets minimization of sum total of allocation values of one to one assignment.
1.1) Mathematical Facts
We have, in this case, an assignment matrix 𝑨 = (𝒂 𝒊𝒋 ) ; 𝒊, 𝒋 𝒊𝒔 𝒂𝒏 𝒊𝒏𝒕𝒆𝒈𝒆𝒓 𝒇𝒓𝒐𝒎 𝟏 𝒕𝒐 𝒎. Let 𝒊 𝒂𝒏𝒅 𝒋 stand for each one of 𝒎 entries for rows 𝑹 𝟏 , 𝑹 𝟐 , 𝑹 𝟑 , . . . . . . . , 𝑹 𝒎 and 𝑪 𝟏 , 𝑪 𝟐 , 𝑪 𝟑 , . . . . . . . , 𝑪 𝒎 for rows and columns respectively. This suggests that the assignment matirx is a square matrix of order 𝒎 × 𝒎 𝒂𝒏𝒅 𝒕𝒉𝒆𝒓𝒆 𝒂𝒓𝒆 𝒎 𝟐 cells. Let each cell value be called 𝑪 𝒊𝒋 for each 𝒊 𝒂𝒏𝒅 𝒋. We have for each 𝑹 𝒊 a unique 𝑪 𝒋 with 𝑪 𝒊𝒋 -as an assignment value of corresponding (𝒊, 𝒋) 𝒕𝒉 cell. A special case of Transportation problem calls for exactly 𝒎 allocated cells. It is a case of highly degenerate solution in which instead of 𝐦 + 𝐦 -𝟏 = 𝟐𝐦 -𝟏allocations, we have exactly 𝐦 allocations. Here we have the targeted objective that the sum total of all 𝑪 𝒊𝒋 ;
𝒇𝒐𝒓 𝒆𝒂𝒄𝒉 𝒊 𝒕𝒉𝒆𝒓𝒆 𝒊𝒔 𝒆𝒙𝒂𝒄𝒕𝒍𝒚 𝒐𝒏𝒆 𝒋 -𝒊 , 𝒋 𝒇𝒓𝒐𝒎 𝟏 𝒕𝒐 𝒎 ; 𝒘𝒉𝒆𝒓𝒆 𝒎 ∈ 𝑵, must be minimum.
1.2) Operation Moded
Hungerian method is decades old and has standard procedural routine which after a finite number of iterative steps descends to an optimal basic feasible solution which is surely degenerate and may suggest multiple optimality. We have, after many rounds of logical attempts, concluded to a novel approach. This method first finds a basic feasible solution which may be optimal and if not, then on applying confirmatory tests of search and reshuffling tends to optimality.
1.3) About the new approach
As described earlier, we have 𝒎 rows 𝑹 𝟏 to 𝑹 𝒎 and 𝒎 columns designated as 𝑪 𝟏 to 𝑪 𝒎 . Also we search for such cells (𝑹 𝒊 , 𝑪 𝒋 )/(𝒊, 𝒋) cell processing the assignment values 𝑪 𝒊𝒋 [for one 𝒊 value there is exactly one uniquely determined -𝒋 𝒂𝒏𝒅 𝒋 ∈ 𝟏 𝒕𝒐 𝒎] so that the sum 𝒛 = ∑ ∑ 𝑪 𝒊𝒋 which is minimum.
1.3.1) General Format
In this section we describe the general format and keep on gradually adding, further aspects of the Jha algorithm.
2.1) How does it work?
We begin towards the direction of finding a basic feasible solution. Each step towards the solution is parallely sounded by an illustration.
Step 1-Column Minimum
We find minimum 𝐂 𝐢𝐣 value of each column and note the same below the horizontal line segment drawn underneath each column.
Step 2 -Set of Minimum Values
At the end of step 1, we have set of 𝐦 values -Minimum sought out from each one of 𝐦 columns. Arrange all these values in ascending order. Let this be the set 𝐌 𝟏 = {𝐦 𝟏 , 𝐦 𝟐 , . . . . . . , 𝐦 𝐦 } ;
Where 𝐦 𝟏 ≤ 𝐦 𝟐 ≤. . . . . . ≤ 𝐦 𝐦 Each 𝐦 𝐢 corresponds to exactly one column value (minimum) from all given columns.
Step 3 -Reformatting the matrix Now we arrange all the columns in correspondence of the ascending order in coordination with members of the set
The new format may look as follows: Step 4 -Search for column Minima and assign Here in this section we proceed to find a basic feasible solution. Observe the first column 𝐊 𝟏 and find minimum entry ; mark it and assign it to that associated row -say 𝐑 𝐢 ; 𝐢 = 𝟏 𝐭𝐨 𝐦. Delete or discard the particular row and the first column from the matrix.
Step 5 -Basic Feasible Solution At the end, on completion of step -4. we repeat the same procedure and move towards feasible solution. Once the minimum is selected and concerned row and the first column (𝑹 𝒊 , 𝑲 𝟏 ) are discarded, we search for minimum entry from the remaining columns -in this case the second column. Again find the set of minimums from all the columns.
Let the set of minimums be 𝑴 𝟐 = {𝒎 𝟐 , 𝒎 𝟑 , . . . . . . , 𝒎 𝒎 } Arrange elements of this set 𝑴 𝟐 in ascending order and rearrange the columns if required. Now, find the minimum from the second column and mark it. Also discard the second columns and the row say 𝑹 𝒊 (𝒊 ≠ 𝒋) corresponding to the minimum entry of the second column. Keep on repeating the above routines for all the remaining columns.
Step 6: Identifying the BFS At the end we have the matrix showing ordered minimum. Enlist it is as follows
Step 7 -Optimality Check In this final step -7, we show optimality check to find the optimal (minimum) sum of all the 𝐦 𝐢 or 𝐂 𝐢𝐣 values for 𝐢 , 𝐣 ∈ 𝟏 to 𝐦, so that the sum total reaches optimality. This was required from the equation -1. In this section we show the procedure by logical illustration. consider, from the above list the highest of 𝐂 𝐢𝐣 entry and other components as shown below. and repeat the above steps. 8. Repeat the above procedure for remaining entries -most possibly some higher 𝐜 𝐢𝐣 value to 𝐜 𝟑𝟐 value this may need the same treatment of reshuffling. This will be clear by the illustration.
2.2) Illustration
We give an illustration to sound the above procedure. Consider the assignment matrix. We want to allocate some c ij -column value to each row R i so that the sum value of allocation is minimum. In this way we complete optimality check and finally after some iteration reach on the optimal solution found as follows: Now at this stage there cannot be further compression as all entries have reached (can be verified) to its minimum.
Conclusion
This new method of fixing optimal allocation has proved faster and effective in solving assignment matrix. This has been verified in number of cases and still remains open for discussion. This also indicates the case of multiple optimal solution if it exists. Maximization problems can also be solved by this method on finding opportunity loss matrix.
References
- Afroz HD, Dr. Hossen MA. New Proposed Method for Solving Assignment Problem and Comparative Study with the Existing Methods, IOSR Journal of Mathematics (IOSR-JM). 2017;13(2):84-88. e-ISSN: 2278-5728, pISSN: 2319-765X.
- Dr. Sharma VK, Sachdeva P. Comparative Study of Various Approaches for Solving the Assignment Problem, IJFANS International Journal of Food and Nutritional Sciences, UGC CARE Listed (Group -I) Journal. 2022;11:10.
- Gothi MM, Patel RG, Patel BS. Optimal Solution To The Assignment Problem, Annals of Mathematics and Computer Science. 2023;16:112-122. ISSN: 2789-7206,
- Supian S, Wahyuni S, Nahar J, Subiyanto. "Optimization of Personnel Assignment Problem Based on Traveling Time by Using Hungarian Methods: Case Study on the Central Post Office Bandung",4th International Conference on Operational Research (Interi OR), IOP Conf. Series: Materials Science and Engineering. 2018;300:012005. Doi:10.1088/1757899X/300/1/012005.
- Prof. Prajapati R, Dr. Haque A, Dr. Jain J, Prof. Singh S. A study on solving Assignment Problem, VIVA-Tech International Journal for Research and Innovation ISSN(Online): 2581-7280, 2021, 1(4).
- Kadhim HJ, Shiker MAK, Al-Dallal HAH. A New Technique for Finding the Optimal Solution to Assignment Problems with Maximization Objective Function, Journal of Physics: Conference Series. 2021;1963:012104.
How this paper connects to the literature. Drag to explore, click any node to open that paper.