Assignment problem (maximization): A new approach

Introduction

In this note we attempt to present the salient features of a new assignment technique designed to reach optimal feasible solution. Keeping the prime objective of efficiency in mind, we aim towards sharing this new approach that focuses on real-life situational problems. The assignment problem (minimization type) is fundamentally an optimization problem in operations research, where the objective is to assign 𝑀 agents to 𝑀 tasks such that the total cost of the assignment is minimized (or profit is maximized) and ensuring that each agent is assigned exactly one of the M tasks.

Traditional Algorithm -The Hungarian Method

In 1955, the Hungarian method, refined by Harold Kuhn, was developed to find the optimal solution for assignment problems, primarily dealing with minimization cases. However, by applying the opportunity loss (or regret) technique, it can solve maximization problems on converting all cell entries of the given maximization assignment problem to opportunity loss matrix and applying the standard minimization algorithm to the resulting matrix. In this framework, both minimization and maximization assignments fall under the same general structure of the Hungarian Method, though this conversion to opportunity loss matrix adds computational overhead.

Mathematical Foundation

The Hungarian Method solves an assignment problem represented by an 𝑀 × 𝑀 matrix (where 𝑀 ∈ ℕ) with 𝑀 2 entries -each entry denotes the cost (or profit) of assigning a task to an agent. In the assignment problem, a linear programming model, has 𝑀 row and 𝑀 column constraints. With one dependent constraint, this leaves 2𝑀 -1 independent equality constraints. Therefore, a basic feasible solution (B.F.S) has exactly 2𝑀 -1 basic variables. In the B.F.S, exactly 𝑀 cells are assigned, often resulting in a highly degenerate solution. A positive feature of the traditional method is its ability to identify multiple optimal solutions when they exist.

The New Approach -Jha's Method

In this section, we describe the complete procedure for finding a basic feasible solution to the assignment problem (maximization type)

Initial Basic Feasible Solution

We describe the procedure to obtain the Basic Feasible Solution (B.F.S.). Given an 𝑀 × 𝑀 assignment matrix with rows denoted as 𝑅 1 , 𝑅 2 , … , 𝑅 𝑀 and columns as 𝐶 1 , 𝐶 2 , … , 𝐶 𝑀 , the steps are as follows: 1. Identify the maximum entry in the matrix, denoted by 𝑥 𝑖𝑗 .

Mark this entry and eliminate the corresponding 𝑖 th row and 𝑗 th column 2. The elimination results in a reduced square matrix of order (𝑀 -1). Determine the maximum entry in this reduced matrix and eliminate its corresponding row and column. 3. Repeat this procedure iteratively until all rows and columns are eliminated.

Key Observation

On completion of the above operations, we observe that exactly one entry is marked in each row and each column. This procedure yields a basic feasible solution (each agent has been assigned a marked entry in its respective column), which serves as the starting point for applying Jha's optimality test. the above procedure ends up int the following I.B.F.S

Row Entry

As shown above, the result leads to an initial basic feasible solution (I.B.F.S).

Jha's Optimality Test

Upon finding the I.B.F.S as mentioned, we describe the procedure that leads to optimal basic feasible solution. The optimality test examines each marked entry and determines whether improvements are possible.

Test Procedure

Beginning with the first marked entry in the 1 st row and 𝑗 th column; that is 𝑥 1𝑗 .

Identify potential improvements

Search for all values numerically higher than 𝑥 1𝑗 in the 1 st row. If no higher values exist, then 𝑥 1𝑗 , as of now, remains optimal for the 1 st row.

Calculate improvement parameters

For the first higher value 𝑥 1𝑘 found in column 𝑘 (where 𝑘 ≠ 𝑗), calculate:

Examining column impact

For this column 𝑘, identify the current marked entry 𝑥 𝑡𝑘 in column 𝑘 (row 𝑡) and calculate:

Compute net benefit

For each potential improvement, calculate the net benefit as:

Calculate Z values

In the same way continue calculating 𝑍 1 , 𝑍 2 , 𝑍 3 , … for other numerically higher values than 𝑥 1𝑗

Convergence to Optimal Solution

The above mentioned Jha's optimality test is terminated if there is no swap executed (checking on from 𝑅 1 to 𝑅 𝑀 ) After completing Jha's optimality test for each entry in the initial basic feasible solution, the algorithm converges to an optimal basic feasible solution. The test ensures that there are no further beneficial exchanges and yields optimality. It has been concluded that the final marked enteries for each row constitutes the optimal basic feasible Solution. We sound this logic by an illustration Step 2 In the remaining matrix, maximum entry = 24 at cell position (1,5). Mark and eliminate Row 1 and Column 5.

Step 3 Similarly, we get the final matrix with all maximum marked entries in order:

Initial Basic Feasible Solution depicted as follow:

Agent

Step 8: Since a swap occurred before completion of one full iteration, we check again from Row 1.

Examining 1 st row values, the marked value 𝑥 15 = 24, There is no numerically higher entry than 24 in this row. Then Move to next row.

The maximum net gain is -2, but since it's negative, there are no beneficial swaps for row 2. We keep the current assignment 𝑥 21 .

Step 10: Examining 3 rd row values, marked value is 𝑥 34 = 24, no entries numerically greater than 24 exist.We Move to next row.

Step 11: Similarly after examining the remaining rows, we can see that one full full iteration completed without any swaps. Hence, we have reached optimality.

Final Optimal

References

1. Dr. Pradeep J Jha. Operations Research. McGraw Hill Education (India) Private Limited. 2014. ISBN: 978-125-902673-7.
2. Afrooz 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.
3. 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.
4. 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.
5. 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.
6. 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).
7. 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.